esercizio complessità computazionale

Question

Sto leggendo "algoritmi e strutture dati" da Aho, Hopcroft & Ullman, e io sono confuso con l'esercizio 1.12 B:

Qual è la complessità computazionale (espresso in notazione O-grande) di questa procedura Pascal?

procedure mysterious( n: integer );
    var
        i, j, k: integer;
    begin
        for i := 1 to n - 1 do
             for j := i + 1 to n do
                 for k := 1 to j do
                    {mysterious statement of O(1)}
    end

La prego di aiutarmi?

Grazie!

Answer 1

E 'O (n ³ ). L'O-grande mostra come tempo di esecuzione (o memoria o altro) è proporzionale alla dimensione del compito (il coefficiente di proporzionalità è omesso).

volte

In questi casi l'istruzione viene eseguita interna proporzionale a (n ³ ). Mi va da 1 a (n-1) - in modo tutto all'interno viene eseguito il ciclo esterno (n-1) volte. j viene eseguito in media da (n / 2) a (n) - (n-1) * (n / 2) volte in modo tutto all'interno viene eseguito. k viene eseguito in media da 1 a (3/4 * n). Questo diventa (n-1) * (n / 2) * (3/4 * n-1), le esecuzioni della dichiarazione interna. Questo è O (n ³ ).