l'exercice de la complexité de calcul

Question

Je lis "structures de données et algorithmes" de Aho, Hopcroft & Ullman, et je suis confondu avec l'exercice 1,12 B:

Quelle est la complexité de calcul (exprimée en notation Big O) de cette procédure 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

Pourriez-vous s'il vous plaît me aider?

Merci!

Answer 1

Il est O (n ³ ). Le grand-O montre comment le temps d'exécution (ou de la mémoire ou autre) est proportionnelle à la taille de la tâche (le coefficient de proportionnalité est omis).

Dans ce cas, l'instruction est exécutée interne fois proportionnel à (n ³ ). i va de 1 à (n-1) - de sorte que tout à l'intérieur du cycle externe est exécutée (n-1) fois. j va en moyenne de (n / 2) à (n) - donc tout l'intérieur est exécutée (n-1) * (n / 2) fois. k va en moyenne de 1 à (3/4 * n). Cela devient (n-1) * (n / 2) * (3/4 * n-1) exécution de l'instruction interne. Ceci est O (n ³ ).