ho bisogno di calcolare la complessità temporale del seguente codice:Tempo complessità delle nidificato ciclo for
for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
// Some code
}
}
E 'O (n^2)?
Infatti, è O (n^2). Vedi anche un esempio molto simile con lo stesso runtime here.
Sì, i cicli nidificati sono un modo per ottenere rapidamente una notazione O grande.
In genere (ma non sempre) un ciclo annidato in un altro causerà O (n²).
Pensateci, il ciclo interno viene eseguito volte, per ogni valore di i. Il ciclo esterno viene eseguito n volte.
quindi si vede un modello di esecuzione in questo modo: 1 + 2 + 3 + 4 + ... + n volte
Pertanto, possiamo legata al numero di esecuzioni di codice dicendo che, ovviamente, viene eseguito più di n volte (limite inferiore), ma in termini di n quante volte stiamo eseguendo il codice?
Beh, matematicamente possiamo dire che eseguirà non più di n² volte, dandoci uno scenario peggiore e quindi il nostro Big-Oh bound of O (n²). (Per ulteriori informazioni su come possiamo dire matematicamente questo aspetto allo Power Series)
Big-Oh non misura sempre esattamente quanto lavoro si sta facendo, ma di solito fornisce un'approssimazione affidabile dello scenario peggiore.
4 anni dopo Modifica: Perché questo post sembra avere una discreta quantità di traffico. Voglio spiegare più dettagliatamente come abbiamo legato l'esecuzione a O (n^2) usando la serie di potenze
Dal sito: 1 + 2 + 3 + 4 ... + n = (n ² + n)/2 = n²/2 + n/2. Come, quindi stiamo trasformando questo in O (n²)? Quello che stiamo dicendo (fondamentalmente) è n²> = n²/2 + n/2. È vero? Facciamo qualche semplice algebra.
Dovrebbe essere chiaro che n²> = n (non strettamente maggiore di, a causa del caso in cui n = 0 o 1), assumendo che n sia sempre un numero intero.
La complessità di Big O effettiva è leggermente diversa da quella che ho appena detto, ma questo è il senso. In realtà, la complessità di Big O chiede se c'è una costante che possiamo applicare a una funzione in modo che sia più grande dell'altra, per un input sufficientemente grande (Vedi la pagina wikipedia)
Posso fare una piccola domanda qui? cosa succede se la parte "// some code" è un calcolo con complessità O (N), come viene calcolato il risultato? Penso che questo sia il caso comune in cui una funzione chiama un'altra e considera la successiva come una black-box con una certa complessità fornita dalle specifiche? –
@ShawnLe: osservazione perspicace. Nella maggior parte delle ipotesi, si, assumiamo che '// some code' è O (1), e quindi non viene fattorizzato nella complessità di Big O. Se fosse effettivamente O (N), allora la nostra complessità complessiva diventerebbe O (N^3). Pensalo come una moltiplicazione (perché lo è). Per le iterazioni del ciclo esterno di ~ N, il ciclo interno itera ~ N volte, con ciascuna iterazione che esegue il lavoro ~ N. N volte N volte N = N^3. – AndyG
Prima considereremo i loop in cui il numero di le iterazioni del ciclo interno sono indipendenti dal valore dell'indice del ciclo esterno.Ad esempio:
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
sequence of statements
}
}
Il ciclo esterno esegue N volte. Ogni volta che viene eseguito il ciclo esterno, il ciclo interno esegue M volte. Di conseguenza, le istruzioni nel ciclo interno eseguono un totale di N * M volte. Quindi, la complessità totale per i due anelli è O (N2).
Un modo rapido per spiegarlo è visualizzarlo.
se entrambi i e j sono da 0 a N, è facile vedere O (N^2)
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
in questo caso, è:
O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O
Questo risulta essere 1/2 di N^2, che è ancora O (N^2)
Grazie per avermi finalmente aiutato a capire come i loop interni con una condizione j <= i risultano in 1/2 N^2. Questo mi ha infastidito per un po 'di tempo. Puoi spiegare come questo è ancora O (N^2)? –
A causa della legge di Moore, possiamo supporre che la velocità di esecuzione dell'algoritmo raddoppia circa ogni 18 mesi. Per questo motivo, quando si analizzano gli algoritmi, è possibile eliminare il coefficiente e concentrarsi sugli algoritmi in termini di n. Fondamentalmente O (n^2) prenderà O (1/2 n^2) in 18 mesi. Man mano che n cresce, il runtime cresce esponenzialmente, dove per un algoritmo lineare, cresce con n. –
Quindi, quello che stai dicendo è che quando si calcola la grande notazione Oh, 1/2 in 1/2 (n^2) non è importante, in parte a causa del fatto che i coefficienti diventano irrilevanti nel tempo? La parte importante di questo termine - di nuovo, in termini di grande Oh - è che è quadratica, non che è un quadratico che si dimezza? –
Sulla prima iterazione del ciclo esterno (i = 1), il ciclo interno verrà iterato 1 volta Sulla seconda iterazione del lato esterno loop (i = 2), l'interno loop itererà 2 volte Sulla terza iterazione del ciclo esterno (i = 3), il ciclo interno verrà ripetuto 3 volte
.
.
Sulla iterazione FINALE del ciclo esterno (i = n), il ciclo interno sarà iterata n volte
Così, il numero totale di volte le istruzioni del ciclo interno verranno eseguiti sarà uguale a la somma dei numeri interi da 1 a n, che è:
((n)*n)/2 = (n^2)/2 = O(n^2) times
duplicati di http://stackoverflow.com/questions/362059/big-o-of-this-nested-loop –
la mia domanda non è esattamente un duplicato di quello a cui ti sei collegato ma è una domanda comune quindi immagino che venga chiesto in molte forme. – yyy
Correlati: [Come trovare la complessità temporale di un algoritmo] (https://stackoverflow.com/q/11032015) – Dukeling