exercice 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) 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 aide-moi?

Merci!

Answer 1

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

Dans ce cas, l'instruction interne est exécutée fois proportionnelle à (n). Je vais de 1 à (n-1) - donc tout ce qui est à l'intérieur du cycle externe est exécuté (n-1) fois. j court en moyenne de (n/2) à (n) - donc tout à l'intérieur est exécuté (n-1) * (n/2) fois. k court en moyenne de 1 à (3/4 * n). Ceci obtient (n-1) * (n/2) * (3/4 * n-1) exécutions de l'instruction interne. C'est O (n).