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 caso migliore e medio) di un algoritmo?
Sì, puoi applicarlo ad altri casi.
Big-Oh dice fondamentalmente "non importa come impili il mazzo contro questo algoritmo, nel peggiore delle ipotesi le sue prestazioni si ridurranno in questo modo rispetto all'input."
Omega è simile, ma significa "non importa quanto sei bravo a fare i suoi input, nella migliore delle ipotesi le sue prestazioni non possono scalare meglio di questa rispetto all'input."
Ad esempio, quicksort è un algoritmo di ordinamento popolare. In realtà è O (n 2 ) perché nel peggiore dei casi ha una prestazione quadratica (scelta pivot errata). Nel migliore dei casi è Ω (n log 2 n) che è in realtà il migliore che un algoritmo di ordinamento di uso generale possa eventualmente raggiungere.
Big-Oh descrive il tasso di crescita di un insieme di funzioni confrontandolo con il tasso di crescita di un'altra funzione. Cosa queste funzioni significano è totalmente irrilevante per Big-Oh. Potrebbe essere una funzione che descrive la complessità temporale del caso peggiore di un algoritmo. Potrebbe essere una funzione che descrive la complessità temporale di best-case di un algoritmo. Potrebbe essere una funzione che descrive la complessità temporale del caso medio di un algoritmo. Potrebbe essere una funzione che descrive la complessità temporale amortizzata nel caso peggiore di un algoritmo. Potrebbe essere una funzione che descrive la peggiore complessità step di un algoritmo. Potrebbe essere una funzione che descrive la peggiore complessità di spazio di un algoritmo. Potrebbe essere una funzione che descrive la quantità di umani nel mondo. Potrebbe essere una funzione che descrive la quantità di denaro che un film produce in relazione al suo costo di produzione.
Sicuramente le tre notazioni principali sono:
"Big-Oh" significa che la tua funzione è sempre < = c * f (x) per alcuni costanti c e valori maggiori di alcuni x.
"Big-Omega" significa che la tua funzione è sempre > = c * f (x) per alcuni costanti c e valori maggiori di alcuni x
"Big-Theta" che viene usato per descrivere un limite superiore e inferiore stretto, il che significa che è sia Big-Oh che Big-Omega. Per mostrare Big-Theta devi mostrare che sia Big-Oh che Big-Omega sono uguali.
E poi, a parte questo, a volte sentirai parlare del "caso peggiore del caso migliore" o "caso migliore del caso peggiore" ecc.
E alla persona di cui sopra che parla di ordinamento rapido, per quanto riguarda l'ordinamento liscio?
Leggi altre domande sui tag algorithms big-o algorithm-analysis