Big O per loop while

Question

Ho avuto questa domanda per il mio incarico l'altro giorno, ma non ero ancora sicuro se avessi ragione.

for(int i =1; i <n; i++) //n is some size 
{    
    for(j=1; j<i; j++) 
    { 
     int k=1; 

     while (k<n) 
     { 
      k=k+C; //where C is a constant and >=2 
     } 
    } 
} 

So che i cicli nidificati sono O (n^2) ma non ero sicuro del ciclo while. Ho assunto che l'intero codice sarà O (n^3).

Answer 1

int k=1; 

    while (k<n){ 
     k=k+C     //where C is a constant and >=2 
    } 

Questo richiederà (n-1)/C passi: scrivere u = (k-1)/C. Poi, k = Cu + 1 e la dichiarazione diventa

u=0; 
while(u < (n-1)/C) { 
    u=u+1 
} 

Da qui il ciclo while è O(n) (dal C è costante)

EDIT: Vorrei provare a spiegare il contrario.

Inizia con una variabile fittizia u. Il ciclo

u=0; 
while(u < MAX) { 
    u = u+1 
} 

corre MAX volte.

Quando si lascia MAX = (n-1)/C, il ciclo è

u=0; 
while(u < (n-1)/C) { 
    u=u+1 
} 

E che corre (n-1)/C volte.

Ora, il controllo u < (n-1)/C è equivalente a C*u < n-1 o C*u + 1 < n, in modo che il ciclo è equivalente a

u=0; 
while(C*u + 1 < n) { 
    u=u+1 
} 

Ora, supponiamo che abbiamo riscritto questo ciclo in termini di una variabile k = C * u + 1. Poi,

u=0; 
k=1; // C * 0 + 1 = 1 

Il ciclo sembra

while(C*u + 1 < n) { 
while(k < n) { 

e la condizione interna è

u=u+1 
    k=k+C //C * (u+1) + 1 = C * u + 1 + C = old_k + C 

Mettere tutto insieme:

int k=1; 

    while (k<n){ 
     k=k+C 
    } 

prende (n-1)/C passi.

Answer 2

Il ciclo interno è letteralmente O(n/C)=O(n), quindi sì, nel complesso è O(n^3) (il secondo ciclo ha un limite superiore di O(n))

Answer 3

Beh, si avrebbe bisogno di guardare quante volte il corpo del ciclo, mentre viene eseguito per un dato valore di n e C. Per esempio n è 10 e C è 3. Il corpo dovrebbe eseguire 3 volte: k = 1, k = 4, k = 7. Per n = 100 e C = 2, il corpo dovrebbe eseguire 50 volte: k = 1,3,5,7,9, ..., 91,93,95,97,99. Si tratta di contare da C fino al n. Dovresti essere in grado di calcolare la complessità del Big-O da quella chiave.

Answer 4

Formalmente, si può procedere con la seguente metodologia (Sigma Notation):

Dove a simboleggia il numero di operazioni costanti all'interno del ciclo più interno (a = 1 se si desidera contare il numero esatto di iterazioni).