Domande con tag 'big-o'

domande con tag
2
risposte

In che modo la notazione O grande indica il limite superiore di una funzione? [duplicare]

Supponiamo di avere una funzione, f (n) = n + 10. Diciamo che f (n) ∈O (n), che significa O (n) rappresenta il limite superiore della funzione. È anche vero che f (n) ∈O (n 2 ) o f (n) ∈O (n 3 ) e così via. Quindi, come possiamo dire c...
posta 10.01.2015 - 20:17
5
risposte

La ricerca binaria sembra superiore, perché il comitato di C ++ ha ancora trovato nella libreria dell'algoritmo?

Desidero cercare un numero intero in un vettore di numero intero. Ho due candidati per il lavoro: Ricerca binaria Trova Sembra che Ricerca binaria sia il miglior candidato per il lavoro, anche se devo ordinare il vettore, il t...
posta 09.02.2014 - 12:19
2
risposte

Cosa si intende per trovare costanti reali e intere nella notazione Big Oh?

Dal mio libro "Strutture dati e algoritmi in Java: Sesta edizione" la definizione di Big Oh è la seguente: Let f(n) and g(n) be functions mapping positive integers to positive real numbers. We say that f(n) is O(g(n)) if there is a real...
posta 27.01.2018 - 20:08
3
risposte

Big-O quando il valore numerico del caso peggiore è noto

Se ho un algoritmo e una parte di esso ha un valore numerico noto nel caso peggiore, che è ragionevolmente piccolo rispetto al resto del problema, è ok sostenere che la parte sia O (1)? es. Se parte dell'algoritmo prevede la costruzione di un...
posta 06.09.2017 - 11:59
2
risposte

Big O Notazione di un esempio

Il mio professore ha dato questo esempio in una conferenza: Example: Given an integer N, print out the values 1…N. for (int i=1; i<=N; i=i+1) { System.out.print(i); } Il professore ha detto che il ciclo era O (n) perché stampava...
posta 29.01.2016 - 17:04
2
risposte

Analisi della complessità temporale per la relazione di ricorrenza

Mi è stato chiesto di capire l'analisi della complessità temporale per la seguente relazione di ricorrenza T(n) = 4*T(n-1) + c . Fondamentalmente, ho fatto una sostituzione .. T(n-1) = 4 * T(n-2) + c e così via .. T(n) = 4^k T(1) +...
posta 03.02.2015 - 14:41
3
risposte

Notazione Big-O per altri casi

Stavo leggendo le risposte a una domanda Semplice spiegazione inglese di Big O Da quello ho capito che la notazione Big-O è solo un "limite superiore" della complessità di un algoritmo? Ma possiamo applicarlo ad altri casi (vale a dire il c...
posta 08.01.2015 - 21:41
2
risposte

Tempo di esecuzione di semplici cicli for

Sto leggendo gli algoritmi e ne capisco la maggior parte, una cosa su cui posso ancora confrontarmi è qualcosa di semplice come i tempi di esecuzione su diversi for-loop. A tutti sembra che sia facile, tranne me e quindi cerco aiuto qui. Attu...
posta 15.08.2014 - 16:21
1
risposta

Il mio ragionamento per determinare il Big-O di questo algoritmo è corretto?

Prendi il seguente algoritmo con due sezioni separate e le sezioni non si influenzano a vicenda (la funzione non è ricorsiva). void algorithm(int x) { // This section of the algorithm has linear growth... O(x) // This section of the alg...
posta 22.04.2018 - 22:07
1
risposta

Quale sarebbe il tipo migliore da utilizzare su qualcosa con "blocchi" ordinati?

Immagina un mazzo ordinato di carte N tagliate K volte spostando le carte X dall'alto verso il basso (X è una quantità diversa / casuale ogni volta, X è sempre < N) - quale sarebbe il migliore modo di ordinare questo, sapendo che ci sono "pez...
posta 11.12.2014 - 21:20