Qual è la complessità di questo ciclo triplo annidato?

Question

Ho cercato un po 'su StackOverflow e ho capito la complessità fino al punto del j-loop, che è O(n2). Tuttavia con l'aggiunta annidata del k-loop, sono confuso dal motivo per cui la complessità diventa O(n3). Qualcuno può aiutarmi a capire questo?

Dalla mia comprensione, l'i-loop ha n iterazioni e il j-loop ha 1 + 2 + 3 + ... + n iterazioni n*(n+1)/2 che è O(n2).

for(i = 1; i < n; i++) { 
    for(j = i+1; j <= n; j++) { 
     for(k = i; k <= j; k++) { 
      // Do something here... 
     } 
    } 
} 

EDIT: Grazie per il vostro aiuto ragazzi :) Balthazar, ho scritto un pezzo di codice al quale incrementerà i contatori a seconda di quale circuito in cui si trovano, un po 'un modo rozzo di per passo passo:

#include <iostream> 

int main(int argc, const char * argv[]) 
{ 
    int n = 9; 
    int index_I = 0; 
    int index_J = 0; 
    int index_K = 0; 
    for (int i = 1; i < n; i++) { 
     for (int j = i+1; j <= n; j++) { 
      for (int k = i; k <= j; k++) { 
       index_K++; 
      } 
      index_J++; 
     } 
     index_I++; 
    } 
    std::cout << index_I << std::endl; 
    std::cout << index_J << std::endl; 
    std::cout << index_K << std::endl; 
    return 0; 
} 

ho eseguito questo codice da n = 2 per n = 9 con incrementi di 1 e hanno ottenuto la seguente sequenza:

Dai contatori, si può quindi vedere che: i = n-1 dando la complessità di O (n) e j = ((n-1) * n)/2 dando la complessità O(n2). Un modello per la K era difficile da individuare, ma si sa che K dipende J, quindi:

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6 dando una complessità di O(n3)

Spero che questo aiuterà le persone in futuro.

EDIT2: grazie Dukeling per la formattazione :) Trovato anche un errore nell'ultima riga, corretti ora

Answer 1

Date un'occhiata a this esempio per valutare caso peggiore complessità.

In sostanza, se lo si valuta riga per riga, si otterrà qualcosa come O (n^3/C), dove C è una costante, normalmente saltata in tali valutazioni, che porta a O (n^3) .

Answer 2

il k-loop ha O (ji) complessità

il j-loop ha O ((ni) * (ni)) complessità

l'i-loop è O (n * n * n) = O (n^3) complessità

in ogni caso, si sa che non è O (n^2) perché i primi due cicli sono O (n^2) e non è superiore a O (n^3)) perché ci sono solo 3 loop

Answer 3

Questo è abbastanza difficile da spiegare senza diagrammi, ma ogni ciclo annidato eseguirà un "n" numero di volte prima di restituire l'iterazione al pa affitto.

Così come sottolinea lo jambono, ogni ciclo annidato richiede confronto/valutazione per ogni iterazione di "n". Quindi "n" viene confrontato con le variabili locali in ogni ciclo (n * n * n) rendendo O (n^3).

Inserire il codice in un debugger per un'indicazione visiva di come questa complessità viene elaborata dalla macchina.

Answer 4

Se siete abituati a Sigma notazione, ecco un modo formale per dedurre la complessità temporale dell'algoritmo (le normali cicli annidati, appunto):

NB: le semplificazioni formula potrebbe contenere errori Se rilevi qualcosa, per favore fammelo sapere.

Answer 5

Prima considereremo i loop in cui il numero di iterazioni del ciclo interno è indipendente 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 dei due anelli è O (N2).
Analogamente la complessità per i tre anelli è O (N3)