Questo è il mio primo corso in strutture dati e ogni lezione/conferenza TA, parliamo di O(log(n)). Questa è probabilmente una domanda stupida, ma sarei grato se qualcuno possa spiegarmi esattamente cosa significa!Differenza tra O (n) e O (log (n)) - che è migliore e che cosa è esattamente O (log (n))?
vuol dire che la cosa in questione (tempo di solito in esecuzione) scale in un modo che è coerente con il logaritmo della sua dimensione di ingresso.
Big-O notation non significa un esatto equazione , ma piuttosto una vincolato. Ad esempio, l'uscita delle seguenti funzioni è tutto O (n):
f(x) = 3x
g(x) = 0.5x
m(x) = x + 5
Perché come si aumenta x, le loro uscite tutti aumentare linearmente - se c'è un rapporto di 6: 1 tra f(n) e g(n), ci sarà anche essere approssimativamente un rapporto 6: 1 tra f(10*n) e g(10*n) e così via.
Per quanto riguarda se O(n) o O(log n) è meglio, prendere in considerazione: se n = 1000, quindi log n = 3 (per log-in base 10). Quale preferiresti far eseguire l'algoritmo: 1000 secondi o 3 secondi?
Ben spiegato. Inoltre, vorrei aggiungere alcune informazioni su ciò che un logaritmo è anche per coloro che non lo sanno. log n in informatica significa, l'esponente avrei bisogno di alzare il numero 2 per ottenere n. Quindi, immagina, se n = 16. Il nostro esponente sarebbe molto molto più piccolo del valore reale n. Sarebbe 4. Spero che questo abbia un senso. Nell'esempio sopra riportato da Amber, lei sta dando un esempio simile ma sta aumentando 10 alla potenza di 3. –
+1 - La spiegazione più chiara possibile nel minor numero di parole. Grazie. – techfoobar
http://en.wikipedia.org/wiki/Big_oh
O (log n) è meglio.
O (log n) significa che tempo di esecuzione dell'algoritmo dipende dal logaritmo della dimensione di input. O (n) significa che il tempo di esecuzione dell'algoritmo dipende dalla dimensione di input.
fondamentalmente, O (qualcosa) è un limite superiore al numero dell'algoritmo di istruzioni (quelle atomiche). pertanto, O (logn) è più stretto di O (n) ed è anche migliore in termini di analisi degli algoritmi. Ma tutti gli algoritmi che sono O (log n) sono anche O (n), ma non indietro ...
"O (n) è più stretto di O (logn) ed è anche migliore in termini di analisi degli algoritmi" ... chiaramente O (log (n)) è migliore di O (n). Penso che tu intendessi l'altro modo. – LuxuryMode
Silly :) modificato – Eyal
Per l'input di dimensione n, un algoritmo di O(n) eseguirà operazioni perportional a n, mentre un altro algoritmo di O(log(n)) eseguirà passaggi all'incirca allo log(n).
Chiaramente log(n) è inferiore a n quindi l'algoritmo di complessità O(log(n)) è migliore. Dal momento che sarà molto più veloce.
definizione formale:
g (x) = O (f (x)) < => c'è x0 e costante C che per ogni x0 x>, | g (x) | < = C | f (x) |.
Quindi, se si trova l'algoritmo A per il problema P che la sua complessità O (f (n)), si può dire che il numero di passi che l'algoritmo farà, è inferiore o uguale asintoticamente a f (n), quando n è solitamente la dimensione di input. (N può essere qualsiasi cosa)
Per ulteriori approfondimenti: http: //en.wikipedia.org/wiki/Big_O_notation.
Una possibile ripetizione di http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278 – sank
Whoa, 1429 upvotes? Sarò felice con la metà di quello per il mio link di Wikipedia. –