Notazione Java Big O di 3 loop nidificati di log (n)

Question

Quale sarebbe la notazione di Big O per i seguenti cicli annidati?

 for (int i = n; i > 0; i = i/2){ 
     for (int j = n; j > 0; j = j/2){ 
      for (int k = n; k > 0; k = k/2){ 
       count++; 
      } 
     } 
    } 

I miei pensieri sono: ogni ciclo è O(log2(n)) così è così semplice come si moltiplicano

O(log2(n)) * O(log2(n)) * O(log2(n)) = O(log2(n)^3) 

Answer 1

Sì, è corretto.

Un modo per capire la complessità di loop nidificati O i cui limiti non dipendono immediatamente l'uno dall'altro è quello di lavorare dall'interno verso l'esterno. Il ciclo più interno funziona O (log n). Il secondo ciclo esegue O (log n) volte e O (log n) funziona ogni volta, quindi O (log n) funziona. Infine, il ciclo più esterno esegue O (log n) volte e O (log n) funziona su ogni iterazione, quindi il lavoro totale svolto è O (registro n).

Spero che questo aiuti!

Answer 2

Sì, hai ragione.

modo semplice per calcolare -

for(int i=0; i<n;i++){ // n times 
    for(int j=0; j<n;j++){ // n times 
    } 
} 

Questo esempio di semplice ciclo nidificato. Qui Big-O di ciascun ciclo O (n) ed è annidato in modo tipico O (n * n) che è O (n^2) effettivo Big-O. E nel tuo caso -

for (int i = n; i > 0; i = i/2){ // log(n) 
    for (int j = n; j > 0; j = j/2){ // log(n) 
     for (int k = n; k > 0; k = k/2){ // log(n) 
      count++; 
     } 
    } 
} 

che è in ciclo annidato in cui ogni anello Big-O è O(log(n)) così ogni complessità insieme sarebbe O(log(n)^3)

Answer 3

In effetti, la tua ipotesi è corretta. È possibile mostrare che metodicamente come il seguente: