Big O Notation Homework - Analisi dell'algoritmo del frammento di codice? [chiuso]

Question

Per i compiti a casa, mi sono stati dati i seguenti 8 frammenti di codice per analizzare e dare una notazione Big-Oh per il tempo di esecuzione. Qualcuno può dirmi se sono sulla strada giusta?

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

Sto pensando a O (N) per il frammento 1

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

O (N) anche per il frammento 2

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O (N ^ 2) per il frammento 3

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

O (N) per il frammento 4

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

O (N ^ 2) per il frammento 5 ma n * n mi sta gettando via un po ', quindi non sono del tutto sicuro

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

O (N ^ 2) anche per il frammento 6

//Fragment 7
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        for(int k = 0; k < j; k++)
            sum++;

O (N ^ 3) per il frammento 7 ma ancora una volta il n * n mi sta gettando via

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

O (N) per il frammento 8

Answer 1

Penso che il frammento 5 sia O (n ^ 3), e allo stesso modo il frammento 7 è O (n ^ 5) *. Sembra anche O (log (n)) per il frammento 8.

Per i problemi n * n, devi eseguire il corpo del ciclo n * n volte, quindi sarebbe O (n ^ 2), quindi componi quello con l'ordine dell'altro codice. Il frammento 8 raddoppia effettivamente il contatore invece di incrementarlo, quindi più grande è il problema, meno lavoro aggiuntivo devi fare, quindi è O (log (n))

* modifica: il frammento 7 è O (n ^ 5), non O (n ^ 4) come pensavo in precedenza. Questo perché sia ??j che k vanno da 1 a n * n. Mi dispiace non averlo scoperto prima.

Answer 2

Il frammento 7 è O (n ^ 5), non O (n ^ 4) come afferma il commento attualmente accettato. Altrimenti, è corretto.

Answer 3

Per il caso 8 prova a scrivere il numero di iterazioni per alcuni valori di N e guarda come appare il modello ... non è O (N)

Answer 4

Sembra che tu sia sulla strada giusta. Per quanto riguarda l'N * N quale effetto pensi che avrebbe? È un altro fattore di N, quindi sarebbe probabilmente un ordine superiore.

Solo un avvertimento, ho visto un altro post come questo ed è stato estremamente votato. Stai attento. Qui è il post.

Answer 5

Sei sulla strada giusta, ma ecco un suggerimento su come le cose potrebbero diventare più chiare lungo la strada. Supponiamo di avere del codice:

for(i = 0; i < n; i++) {
   for(j = 0; j < 100; j++){....}
}

Giusto, considera il fatto che hai un codice a diversi livelli. In questo esempio, finora puoi vedere solo 3 livelli:

1. Il ciclo for esterno che va da 0-n
2. Un altro for-loop che va da 0 a 100
3. All'interno del codice, contrassegnato come ...

In nessun momento dovresti provare a calcolare tutto in 1 volta. È qui che la maggior parte dei principianti commette un errore aritmetico. Calcola individualmente per ogni livello e poi moltiplica tutto insieme.

Buona fortuna!