Qual è la O-grande di un ciclo annidato, dove il numero di iterazioni del ciclo interno è determinato dalla iterazione corrente del ciclo esterno?

Question

Qual è il tempo della complessità O-grande dei seguenti cicli annidati:

for(int i = 0; i < N; i++) 
{
    for(int j = i + 1; j < N; j++)
    {
        System.out.println("i = " + i + " j = " + j);
    }

}

sarebbe O (N ^ 2) ancora?

Answer 1

Sì, è ancora O (n ^ 2), ha un fattore costante più piccola, ma che non pregiudica la notazione O.

Answer 2

Sì. Ricordiamo la definizione di Big-O: O (f (n)) , per definizione, dice che il tempo di esecuzione T (n) ≤ KF (n) per qualche costante k . In questo caso, il numero di passi sarà (n-1) + (n-2) + ... + 0 , riordinando alla somma da 0 a n-1; questo è

T (n) = (n-1) ((n-1) +1) / 2 .

Riorganizzare che e si può vedere che T (n) sarà sempre ≤ 1/2 (n²); dalla definizione, così T (n) = O (n²) .

Answer 3

E 'N al quadrato se si ignora lo System.out.println. Se si assume che il tempo impiegato da che sarà lineare nella sua produzione (che potrebbe anche non essere, ovviamente), ho il sospetto che si finisce con O ((N ^ 2) * log N).

Lo dico di non essere pignoli, ma solo per sottolineare che non solo bisogno di prendere i loop evidenti in considerazione quando si lavora fuori la complessità -. È necessario guardare alla complessità di ciò che si chiama pure

Answer 4

Sì, sarebbe N al quadrato. Il numero effettivo di passaggi sarebbe la somma di 1 a N, che è 0,5 * (N - 1) ^ 2, se non mi sbaglio. Big O prende in considerazione solo il più alto exponant e non costanti, e, quindi, questo è ancora N al quadrato.

Answer 5

Se si ha N = 10, è iterazioni sarebbe: + 9 + 10 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (Questo è:. Dieci iterazioni più nove iterazioni più otto iterazioni ... ecc).

Ora, è necessario trovare in aggiunta quante volte è possibile ottenere un N (10 nell'esempio):

1: (10), 2: (9 + 1), 3: (8 + 2), 4: (7 + 3), 5: (6 + 4). Che è 5 volte ... e poggia 5 iterazioni.

Ora si sa che si dispone di cinque decine + 5:

10 (5) + 5

In termini di f (n) (o N), possiamo facilmente vedere che questo potrebbe essere:

f (n) = n (n / 2) + n / 2 = (n ^ 2) / 2 + n / 2 = (n ^ 2 + n) / 2 ... questa è esattamente la complessità di questi ciclo nidificato.

Ma, considerando il comportamento asintotico di Big O, siamo in grado di eliminare i valori meno significativi di f (n), che sono il singolo n e il denominatore.

Risultato: O (n ^ 2)

Answer 6

AFAIL, essendo iniziata dal circuito interno attraverso quelle esterne è modo adeguato per il calcolo di complessità nested loop.