Perché il grande O è più comunemente associato alle complessità del caso peggiore e al caso medio di una funzione
In mathematics, computer science, and related fields, big-O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.
Questo è il nome che hanno dato al processo di ricerca di quel valore. Puoi leggere ulteriori informazioni al riguardo nella wiki
In matematica, Big O è la notazione per un limite superiore asintotico. La funzione Big-O (con le costanti non specificate inserite con i valori appropriati) è sempre grande almeno quanto la funzione "reale".
Esistono anche notazioni per il limite inferiore asintotico e per un limite stretto. Nel caso strettamente vincolato, con diverse selezioni di costanti, la stessa formula asintotica è sia un limite superiore che un limite inferiore della funzione "reale". Questo è noto come "all'interno di un fattore costante".
Il set completo di notazioni asintotiche è elencato qui ...
Il limite superiore di una funzione corrisponde naturalmente ai requisiti di memoria o tempo peggiore, mentre il limite inferiore della funzione prestazioni peggiore tende a fornire molti risultati migliori del peggiore (è una specie di migliore mancata corrispondenza dei casi peggiori). Allo stesso modo, il limite inferiore corrisponde naturalmente ai requisiti di memoria o di tempo della migliore delle ipotesi, anche se per gli algoritmi ci interessa meno spesso.
Alcuni libri di testo sugli algoritmi (in particolare Cormen et al.) usano molto i limiti stretti.
Si scopre che il limite inferiore del caso peggiore può essere utile, comunque. Ho fatto questa domanda recentemente ...
Perché è esattamente ciò che è stato progettato per scoprire.
Principalmente perché il caso peggiore e il caso medio sono quelli a cui la maggior parte della gente si preoccupa - cosa posso davvero aspettarmi, e qual è la cosa peggiore che potrebbe accadere?
Il caso migliore ha alcuni usi reali - ad esempio, ho visto persone sprecare un sacco di tempo a cercare algoritmi significativamente migliori nei casi in cui se avessero passato 10 minuti pensando al caso migliore, si sarebbero resi conto che ciò che avevano era già (almeno da una prospettiva di complessità asintotica) buono come potevano sperare.
Perché è molto più comune preoccuparsi del caso peggiore del caso migliore.
Generalmente, quando stai pensando alla complessità del tuo algoritmo, non sei in una situazione in cui puoi fare troppe ipotesi sull'input. Pertanto, si dovrà considerare il caso medio (per stimare le prestazioni su un numero elevato di esecuzioni con input arbitrario) o il caso peggiore (per stimare quanto tempo potrebbe impiegare per elaborare input arbitrari). Caso migliore? È raro che ti preoccupi che il tuo programma possa essere eseguito molto rapidamente se sei fortunato.
Naturalmente, si possono immaginare situazioni diverse. Ad esempio, il caso migliore per il famigerato Bubblesort è O (N) se la lista fosse già stata ordinata. Se hai una lista che sai essere quasi ordinata (ad esempio, una lista precedentemente ordinata che ha avuto alcune piccole modifiche apportate ad alcuni elementi), puoi essere certo che Bubblesorting sarà vicino al meglio caso di prestazioni. Ma non useresti mai un Bubblesort per un tipo generale che avrebbe preso un numero arbitrario di elementi mescolati arbitrariamente.
Leggi altre domande sui tag big-o