Complessità di un ciclo double per

Question

Sto cercando di capire la complessità di un ciclo for utilizzando la notazione Big O. L'ho già fatto nelle altre classi, ma questa è più rigorosa delle altre perché è sull'algoritmo attuale. Il codice è il seguente:

for(cnt = 0, i=1; i<=n; i++) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
} 

E

for(cnt = 0, i=1; i<=n; i*=2) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
} 

sono arrivato che il primo ciclo è di O (n) la complessità perché sta attraversando la lista n volte. Per quanto riguarda il secondo ciclo sono un po 'perso. Credo che stia attraversando il ciclo i volte per ogni n che viene testato. Ho assunto (erroneamente) che ciò significa che il ciclo è O (n * i) per ogni volta che viene valutato. C'è qualcosa che mi manca nella mia ipotesi. So che cnt ++ è un tempo costante.

Grazie per l'aiuto nell'analisi. Ogni loop è nel suo spazio, non sono insieme.

Answer 1

Il ciclo esterno del primo esempio esegue n volte. Per ogni iterazione del ciclo esterno, il ciclo interno viene eseguito i volte, quindi la complessità complessiva può essere calcolata come segue: una per la prima iterazione più due per la seconda iterazione più tre per la terza iterazione e così via, più n per l'iterazione n.

1+2+3+4+5+...+n = (n*(n-1))/2 --> O(n^2) 

Il secondo esempio è più complicato: dal i raddoppia ogni iterazione, il ciclo esterno esegue solo Log2(n) volte. Supponendo che n è una potenza di 2, il totale per il ciclo interno è

1+2+4+8+16+...+n 

che è 2^Log2(n)-1 = n-1 per la complessità O(n).

Per n s che non sono potenze di due il numero esatto di iterazioni è (2^(Log2(n)+1))-1, che è ancora O(n):

1  -> 1 
2..3 -> 3 
4..7 -> 7 
8..15 -> 15 
16..31 -> 31 
32..63 -> 63 

e così via.

Answer 2

Speriamo che questo non è lavoro, ma io vedo che almeno fatto un tentativo qui, ecco il mio prendere su questo:

cnt viene incrementato n * (n + 1)/2 volte, che rende l'intero set di entrambi i loop O (n^2). Il secondo ciclo è O (n/2) nella media, che è O (n).

Answer 3

Il primo esempio è O (N^2) e What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop? sarebbe la domanda che risponde a quella in cui la chiave è di notare che il numero di cicli del ciclo interno dipende da n.

Il secondo esempio è probabile O (n log n) poiché il ciclo esterno viene incrementato su una scala diversa rispetto a quella lineare. Guarda la ricerca binaria per un esempio di un caso di complessità logaritmica. Nel secondo esempio, il ciclo esterno è O (log n) e il ciclo interno è O (n) che si combinano per dare una complessità O (n log n).