Da quello che ho raccolto, la notazione O è usata per descrivere la lunghezza di un'operazione. Tuttavia, questo è quanto ho ottenuto. Che cosa è esattamente la notazione O e come sono i più comuni ( O(n) , O(2n) , O(n^2) , O(log n) , ecc)?
Posso capire da dove vieni da qui - sto imparando anche questo, ea volte è davvero utile avere una spiegazione più rilassata di qualcosa quando è nuova. Per favore, tieni presente che sto solo imparando anche questo, ma questo è il modo in cui capisco big-Oh:
Fa parte della notazione asintotica, che è usata per descrivere il tempo di esecuzione di un algoritmo (cioè mette il tempo di esecuzione in un intervallo da best-case (Omega) a worst-case (big-Oh) e possiamo assicurati che l'algoritmo impieghi almeno Omega e al massimo Big-Oh per l'esecuzione)
Big-Oh è il limite superiore, cioè il più lento che l'algoritmo eseguirà mai (con successo)
O (n) è un tempo lineare - Puoi pensare ad esso come camminare su una serie di scale, sinistra-destra-sinistra-destra. Quindi fai un passo su ogni scala (o fai scorrere un elenco una volta)
O (n ^ 2) è il tempo quadratico - ovviamente questo è molto più alto (richiederà più tempo) di O (n). Potresti pensare a questo come se prendessi n passi su ogni scala mentre sali (o se ci sono 8 gradini, dovresti fare 8 passi su ogni scala)
O (log (n)) è tempo logaritmico - questo è il Santo Graal per molti algoritmi (come l'ordinamento, essere in grado di ordinare in O (log (n)) è davvero buono!) . Cercare di descrivere questo nell'analogia delle scale è un po 'complicato, e non credo di averlo capito abbastanza bene da provare :) Ma l'idea generale è che man mano che le scale si allungano, non devi fai molto più lavoro per scalarli, perché in effetti li stai facendo saltare
Per quanto riguarda la base del logaritmo, non importa veramente per la notazione asintotica, perché con la notazione asintotica si sta tentando di descrivere cosa accadrà quando la dimensione (n) diventa veramente davvero grande (anche se spesso è base 2). Tutti i log di log (base > = 2) iniziano ad appiattirsi a valori alti, quindi vinceranno sempre nella fascia alta.
C'è un corso sulla coursera, Design and Analysis of Algorithms, che è appena iniziato questa settimana - una delle prime conferenze fornisce una descrizione di alto livello della notazione asintotica, e l'ultima domanda sul set di problemi della settimana uno mi ha fatto pensare sui tempi di corsa e su cosa batte. Non ci vorrà molto a lanciare l'occhio su questi.
Spero che questo aiuti un po '!
Leggi altre domande sui tag big-o