Il mio insegnante di informatica dice che Big O ha un limite superiore ma nessun limite inferiore. Quando guardo un grafico di un algoritmo mappato usando BigO, non c'è affatto un limite superiore. Il limite superiore va avanti all'infinito. Quindi cosa significa dire che esiste un limite superiore nel contesto di BigO?
BigO è, in poche parole, una misura della complessità dell'algoritmo. Nel migliore dei casi, anche il peggior algoritmo può essere completato in un'unica operazione / iterazione. Tuttavia, le diverse operazioni presentano diverse complessità nella media e nella peggiore delle ipotesi. Queste complessità del caso peggiore potrebbero essere considerate il limite superiore.
Quindi, come possiamo capire il limite superiore?
Un algoritmo avrà durate diverse in base alla dimensione dei dati che sta gestendo. Ad esempio, consideriamo una semplice struttura dati, che potrebbe essere implementata in vari modi (usiamo un array) e decidiamo di voler cercare la struttura per una parte di dati. Il numero di operazioni che devi fare sarà basato sulla dimensione della raccolta di dati. Supponiamo che ci siano n elementi nella struttura.
Un array tipico, nel peggiore dei casi, eseguirà l'iterazione dell'intera raccolta per questo, il che significa che eseguirai fino a n operazioni, risultando in O(n) complessità, quindi hai un limite superiore di n .
Supponiamo che i dati siano ordinati: ora puoi eseguire una ricerca binaria, con conseguente% di operazioni dilog(n), riducendo la complessità con un limite superiore di O(log(n)) . Potrebbe ancora essere completato in una sola operazione, e se n si avvicina a un numero infinito, la complessità si avvicina al tempo di esecuzione infinito. Questo è probabilmente quello che stavi vedendo in classe. Diverse complessità dell'algoritmo si avvicinano a questo livello di esecuzione infinito a velocità diverse (n! > n ^ 2 > n > log (n) > 1).
Modifica: Come per i commenti, si dovrebbe notare che una variazione nella quantità di dati si rifletterà anche in un cambiamento nel tempo di esecuzione in base alla complessità. Gli algoritmi O (1) non cambieranno, quelli logaritmici cambieranno in modo logaritmico, gli algoritmi lineari in modo lineare, ecc. Essenzialmente, il raddoppio della quantità di dati potrebbe NON raddoppiare il tempo di esecuzione. Puoi quadruplicarlo o aumentarlo con un fattore più piccolo o più grande.
Per un esempio più complesso, è necessario più lavoro per capire la complessità, naturalmente, ma questa è l'idea generale:
Il Limite superiore della complessità di un algoritmo descrive come il tempo di esecuzione dell'algoritmo cambia con una variazione nella quantità di dati elaborati nell'operazione, il che significa che spesso un algoritmo più complesso un tempo sempre più lungo (spesso non lineare) da eseguire man mano che aumenta la quantità di dati.
Il caso peggiore ci dà un limite superiore alle prestazioni. Analizzare la peggiore delle ipotesi di un algoritmo garantisce che non andrà mai peggio di quello che noi determinare.
Leggi altre domande sui tag algorithms computer-science big-o