La complessità temporale del ciclo for nidificato

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.

  • Moltiplicare entrambi i lati per 2: 2n²> = n² + n?
  • Espandere 2n² per ottenere: n² + n²> = n² + n?
  • Sottrai n² da entrambi i lati per ottenere: n²> = n?

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