Domanda di runtime del ciclo

Question

Domanda di runtime del ciclo

#1 da (19 voti)
#2 da (5 voti)
#3 da (0 voti)

5

Ho fatto un esame oggi e sento di aver fatto abbastanza bene, tranne che non potevo per la vita di me capire quella che sembra essere una domanda incredibilmente semplice.

Ci è stato chiesto di fornire tempi di esecuzione della notazione theta per alcuni programmi (con dimensione di input n), e questo era uno di questi:

int sum = 0;
for int i = 0; i < n; i++
   for int j = 0; j < i; j++
      sum++

Quindi so che l'iterazione da 0 a n su entrambi i loop renderebbe un tempo di esecuzione O (n ²) ... ma con il secondo ciclo che itera solo alla prima variabile di controllo del ciclo, vorrei Supponiamo che debba essere più veloce ... perché il secondo ciclo non raggiunge mai le iterazioni fino all'ultimo loop-through?

Sto andando fuori di testa se la sua O (n ²) e io pensavamo che questo ...

loops runtime big-o algorithm-analysis

posta Joey Hanlon 06.11.2014 - 22:45

fonte

3 risposte

Leggi altre domande sui tag loops runtime big-o algorithm-analysis

Se sappiamo solo che un video è 720P, 480P o 240P può dirci in modo inequivocabile la risoluzione? Sopraffatto dal complesso progetto C # / ASP.NET in Visual Studio 2008 [chiuso]

score 19 · Answer 1

La classe di complessità è O(n²) .

Spiegazione visiva

Immagina un n·n quadrato che elenca tutti i valori che j assume. Rimuoviamo la diagonale (che ha n voci) e la metà superiore destra perché j non sarà mai più grande o uguale a i . Ci rimane quindi un'area di (n² - n)/2 .

 i  | values of j     | no of j values
----+-----------------+---------------
 0  | · · · · ·  ⋯  · |  0
 1  | 0 · · · ·  ⋯  · |  1
 2  | 0 1 · · ·  ⋯  · |  2
 3  | 0 1 2 · ·  ⋯  · |  3
 4  | 0 1 2 3 ·  ⋯  · |  4
 :  | : : : :    :  : |  :
n-1 | 0 1 2 3 ⋯ n-2 · | n-1
                       =====
                  SUM: (n² - n)/2

Spiegazione matematica

Il ciclo esterno esegue n volte, il ciclo interno i volte. Possiamo scrivere il numero di esecuzioni del corpo del loop interno come &Sum;^m_i=1i con m = n-1 . La somma di tutti i numeri naturali fino a includere m può anche essere scritta come m·(m + 1)/2 (la formula per numeri triangolari ), che porta a n(n-1)/2 .

Conclusione

Utilizzando entrambi i metodi, possiamo determinare che i cicli nidificati hanno una complessità di O((n² - n)/2) = O(n²) .

score 5 · Answer 2

I'm gonna freak out if its O(n²) and I over thought this...

Non esagerare, troppo.

Il ciclo esterno verrà eseguito n volte. Il ciclo interno eseguirà una media di circa (n / 2) volte. Ciò comporta un totale di n ² / 2 valutazioni - o in notazione più precisa, runtime di O (n ²).

Anche questo è abbastanza facile da verificare scrivendo un programma breve / semplice.

score 0 · Answer 3

Per questa particolare situazione, come puoi ricordarla: potresti riscriverla come

for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
        if (j < i)
            do_some_stuff ();

Il loop ora viene eseguito n ^ 2 volte chiaramente. do_some_stuff viene eseguito solo se j < io. Dal momento che j < io o j > io (con il raro caso j == i), j < è vero circa la metà delle volte e do_some_stuff viene eseguito circa n ^ 2/2 volte.

Ora dì che hai un ciclo simile a quello con quattro variabili i, j, k, l. E tu scopri n ^ 4 iterazioni, ma do_some_stuff viene eseguito solo se i < j < k < l. Poiché quattro numeri possono essere organizzati in 24 modi diversi, io < j < k < Succede circa una volta su 24, quindi do_some_stuff viene eseguito n ^ 4/24 volte.

Puoi solo barare: conta quante volte succede qualcosa e stampa i numeri. Inseriscili in un foglio di calcolo. Per esempio nel tuo caso print sum, quindi in un foglio di calcolo inserisci n, sum, sum / n, sum / n ^ 2, sum / n ^ 3, sum / n ^ 4. Scoprirai che uno di questi tende a non cambiare molto quando n diventa grande.