Devo calcolare la complessità temporale del seguente codice:
for (i = 1; i <= n; i++) { for(j = 1; j <= i; j++) { // Some code } } È O (n ^ 2) ?
Sì, i cicli annidati sono un modo per ottenere rapidamente una notazione O grande.
Tipicamente (ma non sempre) un ciclo annidato in un altro causerà O (n²).
Pensaci, il ciclo interno viene eseguito io volte, per ogni valore di i . Il ciclo esterno viene eseguito n volte.
così vedi uno schema di esecuzione come questo: 1 + 2 + 3 + 4 + … + n volte
Pertanto, possiamo limitare il numero di esecuzioni di codice dicendo che ovviamente esegue più di n volte (limite inferiore), ma in termini di n quante volte stiamo eseguendo il codice?
Bene, 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 alla serie Power )
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 buona quantità di traffico. Voglio spiegare più dettagliatamente come abbiamo legato l’esecuzione a O (n²) usando la serie di potenze
Dal sito web: 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à effettiva di Big O è leggermente diversa da quella che ho appena detto, ma questo è il succo di ciò. In realtà, la complessità di Big O chiede se c’è una costante che possiamo applicare a una funzione in modo tale che sia più grande dell’altra, per un input sufficientemente grande (vedi la pagina di wikipedia )
Un modo rapido per spiegarlo è visualizzarlo.
se entrambi i e j sono da 0 a N, è facile vedere O (N ^ 2)
OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO
in questo caso, è:
O OO OOO OOOO OOOOO OOOOOO OOOOOOO OOOOOOOO
Questo risulta essere 1/2 di N ^ 2, che è ancora O (N ^ 2)
In effetti, è O (n ^ 2). Vedi anche un esempio molto simile con lo stesso runtime qui .
Prima considereremo i loop in cui il numero di iterazioni del ciclo interno è indipendente dal valore dell’indice del ciclo esterno. Per 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).
Alla 1a iterazione del ciclo esterno (i = 1), il ciclo interno eseguirà l’iterazione 1 volte Nella seconda iterazione del ciclo esterno (i = 2), il ciclo interno eseguirà l’iterazione di 2 volte Nella terza iterazione del ciclo esterno (i = 3), il ciclo interno verrà ripetuto 3 volte
.
.
Durante l’iterazione FINALE del ciclo esterno (i = n), il ciclo interno verrà ripetuto n volte
Quindi, il numero totale di volte in cui le istruzioni nel ciclo interno saranno eseguite sarà uguale alla sum dei numeri interi da 1 a n, che è:
((n)*n) / 2 = (n^2)/2 = O(n^2) times