Ho bisogno di aiuto per capire come trovare il Big-Oh di un segmento di codice

Question

La finale di My Computer Science II è domani, e ho bisogno di aiuto per capire come trovare il Big-Oh per segmenti di codice. Ho cercato su internet e non sono riuscito a trovare alcun esempio di come ho bisogno di capirlo.

Ecco un problema dal nostro campione finale:

for(int pass = 1; i <= n; pass++) 
{ 
    for(int index = 0; index < n; index++) 
     for(int count = 1; count < n; count++) 
     { 
      //O(1) things here. 
     } 
    } 
} 

Siamo tenuti a trovare l'ordine (Big-Oh) dell'algoritmo.

Io penso che sarebbe O (n^3), ed ecco come sono arrivato a questa conclusione

for(int pass = 1; i <= n; pass++) // Evaluates n times 
{ 
    for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
     for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
     { 
      //O(1) things here. 
     } 
    } 
} 
// T(n) = (n) + (n^2 + n) + n^3 
// T(n) = n^3 + n^2 + 2n 
// T(n) <= c*f(x) 
// n^3 + n^2 + 2n <= c * (n^3) 
// O(n) = n^3 

Non sono solo sicuro se sto facendo in modo corretto. Qualcuno può spiegare come valutare un codice come questo e/o confermare la mia risposta?

Answer 1

Sì, è O(n^3). Tuttavia:

for(int pass = 1; pass <= n; pass++) // Evaluates n times 
{     //^^i should be pass 

    for(int index = 0; index < n; index++) //Evaluates n times 
     for(int count = 1; count < n; count++) // Evaluates n-1 times 
     { 
      //O(1) things here. 
     } 
    } 
} 

Poiché avete tre strato di cicli for innestati, il ciclo annidato verrà valutata n *n * (n-1) volte, ogni operazione all'interno del più ciclo for interno richiede O (1) tempo, quindi in totale si hanno n^3 - n^2 costante operazioni, che è O(n^3) in ordine di crescita.

Una buona sintesi di come misurare ordine di crescita nella notazione O-grande può essere trovato qui:

Big O Notation MIT

Citando parte dal file di cui sopra:

Cicli annidati

for I in 1 .. N loop 
    for J in 1 .. M loop 
     sequence of statements 
    end loop; 
end loop; 

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à è O (N * M). In un caso speciale comune in cui lo stato di arresto dell'anello interno è J <N invece di J <M (vale a dire, il ciclo interno esegue anche N volte), la complessità totale per i due anelli è O (N^2).

Razionale simile può essere applicato nel tuo caso.

Answer 2

Hai assolutamente ragione. È O (n^3) per il tuo esempio.

Per trovare il tempo di esecuzione di Big Oh di qualsiasi segmento di codice, dovresti pensare a quante volte il pezzo di codice fa O (1) cose.

Permettetemi di semplificare il vostro esempio per dare un'idea migliore di questo:

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
    { 
     //O(1) things here. 
    } 
} 

Nel caso di cui sopra, il ciclo interno viene eseguito n volte per ogni esecuzione del ciclo esterno. E il tuo ciclo esterno viene eseguito n volte. Questo significa che stai facendo n cose, n numero di volte. Rendendolo O (n^2).

Un'altra cosa da considerare è che Big Oh è un limite superiore. Ciò significa che dovresti sempre pensare a cosa succederà al codice quando hai un grande input (nel tuo caso, un grande valore di n. Un'altra implicazione di questo fatto è che moltiplicare o aggiungere per costanti non ha alcun effetto sul Big Oh bound. Ad esempio:

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < 2*n; count++) // Runs 2*n times 
    { 
     //O(1) things here. 
    } 
} 

Il tempo di esecuzione Big Oh di questo codice è anche O (n^2) da O (n * (2n)) = O (n^2)

. Controlla anche questo: http://ellard.org/dan/www/Q-97/HTML/root/node7.html