Caso peggiore vs O (n)

Question

C'è una differenza tra la dichiarazione "caso peggiore tempo di esecuzione di un algoritmo A" e "tempo di un algoritmo Una corsa è O (n)"?

Quello che penso "non c'è differenza", perché, nel caso peggiore è il picco di tempo che la funzione può assumere, O (n) significa che la funzione è "delimitata da" in esecuzione. Sia dare lo stesso significato.

La speranza mia logica è corretta.

Answer 1

Non c'è differenza.

Un algoritmo è O (f) non è precisa: devi dire un'alogirthm è O (f) nella sua migliore peggiore dei casi / / fuochi d'artificio. Si può dire che è O (f) quando migliore, peggiore e fuochi d'artificio sono gli stessi, ma non è così comune.

Answer 2

Sono d'accordo con il tuo sentimento, ma ci sono algoritmi comuni (quicksort per esempio) che hanno un tempo previsto molto meglio di loro tempo caso peggiore. Si potrebbe rivendicare quicksort è O (n ^ 2) caso peggiore, ma è ancora aspetta che sia O (N * log N) quasi sempre (almeno per un'implementazione buono).

E 'anche si complica con algoritmi che hanno un comportamento ammortizzato. Si potrebbe ottenere O (N) o O (log N) per una particolare operazione, ma molte operazioni di fila sarà sempre O (1) nel senso ammortizzato. albero splay e Finger alberi sono buoni esempi in questa categoria.

Answer 3

Tempo di esecuzione come una misura assoluta di solito è meno importante di come quel tempo aumenta quando si aggiungono altri dati . Ad esempio, un algoritmo riesce comunque sempre 5 secondi per elaborare 100 articoli, 10 secondi per elaborare 200 articoli e così via, si dice che sia O (N) in quanto il tempo di calcolo aumenta linearmente con il formato di dati. Se un secondo algoritmo voluti 5 * 5 = 25 secondi per elaborare tali 200 articoli invece, potrebbe essere classificato come O (N ^ 2). Non c'è "picco in esecuzione di tempo", in quanto il tempo di esecuzione aumenta sempre quando si getta più dati a esso.

In effetti, grande O è un limite superiore - così si potrebbe dire che il primo algoritmo era O (N ^ 2) e (se N è un limite superiore, N * N è più alto e quindi anche un limite superiore, sia pure un perdente uno). notazione comune per indicare altri limiti include Ω (omega, limite inferiore) e Θ (theta, simultanea inferiore e superiore).

Alcuni algoritmi (ad esempio, Quicksort) esibiscono un comportamento diverso a seconda dei dati alimentati ad esso -. Qui il caso peggiore è O (N ^ 2), anche se di solito comporta come se fosse O (N log N)

Answer 4

C'è una differenza enorme tra quelle stringhe di parole. "Nel peggiore dei casi il tempo di un algoritmo A running" è una clausola sostantivo, non fa alcuna dichiarazione a tutti. "Tempo di esecuzione di algoritmo A è O (n)" è una frase, che ci dice qualcosa su un.