Sto aggiornando la mia teoria di CS, e voglio sapere come identificare l'algoritmo O (log n) complessità. In particolare, esiste un modo semplice per identificarlo?
Conosco O (n), di solito hai un ciclo singolo; O (n ^ 2) è un doppio ciclo; O (n ^ 3) è un ciclo triplo, ecc. Che ne dici di O (log n)?
I know with O(n), you usually have a single loop; O(n^2) is a double loop; O(n^3) is a triple loop, etc. How about O (log n)?
Stai davvero andando nel modo sbagliato qui. Stai cercando di memorizzare quale espressione di O grande va con una determinata struttura algoritmica, ma dovresti davvero contare il numero di operazioni che l'algoritmo richiede e confrontarlo con le dimensioni dell'input. Un algoritmo che scorre su tutto il suo input ha prestazioni O (n) perché esegue il ciclo n volte, non perché ha un singolo ciclo. Ecco un singolo ciclo con prestazioni O (log n):
for (i = 0; i < log2(input.count); i++) {
doSomething(...);
}
Quindi, qualsiasi algoritmo in cui il numero di operazioni richieste è nell'ordine di il logaritmo della dimensione dell'input è O (log n). La cosa importante che l'analisi big-O ti dice è come cambia il tempo di esecuzione di un algoritmo rispetto alla dimensione dell'input: se raddoppia la dimensione dell'ingresso, l'algoritmo richiede un ulteriore passo (O (log n)) , il doppio dei passaggi (O (n)), quattro volte il numero di passaggi (O (n ^ 2)), ecc.
Aiuta a sapere per esperienza che gli algoritmi che dividono ripetutamente il loro input di solito hanno 'log n' come componente delle loro prestazioni? Sicuro. Ma non cercare il partizionamento e saltare alla conclusione che la performance dell'algoritmo è O (log n) - potrebbe essere qualcosa come O (n log n), che è abbastanza diverso.
L'idea è che un algoritmo è O(log n) se invece di scorrere una struttura 1 per 1, dividi la struttura a metà ancora e ancora e fai un numero costante di operazioni per ogni divisione. Gli algoritmi di ricerca in cui lo spazio delle risposte continua a essere diviso sono O(log n) . Un esempio di questo è ricerca binaria , dove continui a dividere un array ordinato a metà ancora e ancora fino a trovare il numero .
Nota: non è necessario che lo split sia diviso a metà.
Gli esempi tipici sono quelli che si occupano di ricerca binaria. Ad esempio, un algoritmo di ricerca binaria è in genere O(log n) .
Se hai un albero di ricerca binario , la ricerca, l'inserimento e l'eliminazione sono tutti O(log n) complessità.
Qualsiasi situazione in cui continui a suddividere lo spazio spesso coinvolgerà un componente log n . Questo è il motivo per cui molti algoritmi di ordinamento hanno una complessità di O(nlog n) , perché spesso partizionano un set e ordinano come vanno.
Se lo desideri come "loop singolo - > O (n), double loop - > O (n ^ 2)", la risposta è probabilmente "Tree - > O (log n)" . Attraversare più accuratamente un albero dalla radice ad una foglia (non tutta!) O viceversa. Tuttavia, queste sono tutte semplificazioni eccessive.
Vuoi sapere se c'è un modo semplice per identificare se un algoritmo è O (log N).
Bene: basta correre e cronometrare. Eseguilo per gli ingressi 1.000, 10.000, 100.000 e un milione.
Se vedi una durata di 3,4,5,6 secondi (o qualche multiplo) puoi tranquillamente dire che è O (log N). Se è più simile a: 1,10,100,1000 secondi, probabilmente è O (N). E se è come 3,40,500,6000 secondi, allora è O (N log N).
Leggi altre domande sui tag algorithms complexity big-o