Se vuoi analizzare questi algoritmi devi definire // dostuff, in quanto ciò può davvero cambiare il risultato. Supponiamo che dostuff richieda un numero O (1) di operazioni costante.
Ecco alcuni esempi con questa nuova notazione:
Per il tuo primo esempio, l'attraversamento lineare: questo è corretto!
O (N):
for (int i = 0; i < myArray.length; i++) {
myArray[i] += 1;
}
Perché è lineare (O (n))? Quando aggiungiamo ulteriori elementi all'input (array) la quantità di operazioni che si verificano aumenta proporzionale al numero di elementi che aggiungiamo.
Quindi se ci vuole un'operazione per incrementare un intero da qualche parte nella memoria, possiamo modellare il lavoro che il ciclo fa con f (x) = 5x = 5 operazioni aggiuntive. Per 20 elementi aggiuntivi, eseguiamo 20 operazioni aggiuntive. Un singolo passaggio di un array tende ad essere lineare. Così sono algoritmi come bucket sort, che sono in grado di sfruttare la struttura dei dati per fare un ordinamento in un singolo passaggio di un array.
Anche il tuo secondo esempio sarebbe corretto e assomiglia a questo:
O (N ^ 2):
for (int i = 0; i < myArray.length; i++) {
for (int j = 0; j < myArray.length; j++) {
myArray[i][j] += 1;
}
}
In questo caso, per ogni elemento aggiuntivo nel primo array, io, dobbiamo elaborare TUTTO di j. Aggiungere 1 a I aggiunge effettivamente (lunghezza di j) a j. Quindi, hai ragione! Questo modello è O (n ^ 2), o nel nostro esempio è in realtà O (i * j) (o n ^ 2 se i == j, che è spesso il caso con operazioni a matrice o una struttura dati quadrata.
Il tuo terzo esempio è dove le cose cambiano a seconda dei dostuff; Se il codice è scritto e fa roba è una costante, in realtà è solo O (n) perché abbiamo 2 passaggi di una matrice di dimensione n e 2n si riduce a n. Gli anelli che si trovano l'uno all'esterno dell'altro non sono il fattore chiave che può produrre codice 2 ^ n; ecco un esempio di una funzione che è 2 ^ n:
var fibonacci = function (n) {
if (n == 1 || n == 2) {
return 1;
}
else {
return (fibonacci(n-2) + fibonacci(n-1));
}
}
Questa funzione è 2 ^ n, poiché ogni chiamata alla funzione produce DUE chiamate aggiuntive alla funzione (Fibonacci). Ogni volta che chiamiamo la funzione, la quantità di lavoro che dobbiamo fare raddoppia! Cresce molto velocemente, come se si tagli la testa da un'idra e ne spuntassero due nuovi ogni volta!
Per il tuo esempio finale, se stai usando un ordinamento nlgn come merge-sort hai ragione che questo codice sarà O (nlgn). Tuttavia, è possibile sfruttare la struttura dei dati per sviluppare ordinamenti più rapidi in situazioni specifiche (ad esempio, oltre un intervallo di valori noto e limitato come 1-100). È corretto pensare, tuttavia, che il codice di ordine più elevato prevalga; quindi se un ordinamento O (nlgn) è vicino a qualsiasi operazione che richiede meno di tempo O (nlgn), la complessità temporale totale sarà O (nlgn).
In JavaScript (almeno in Firefox) l'ordinamento predefinito in Array.prototype.sort () è infatti MergeSort, quindi stai guardando O (nlgn) per lo scenario finale.