Séance 4
Indications de solutions

Cette page présente des solutions pour certains des exercices de la séance 4.

1. Vrai ou faux ?

   1000 n2 + 17 n3 ∈ O(n2).	FAUX. Le terme dominant est n3.
   1000 n2 + 17 n3 ∈ Ω(n).	VRAI.
   n log n ∈ O(n).	FAUX.
   2n ∈ Ω(n2).	VRAI. n2 croît beaucoup moins vite que 2n.
   Si f ∈ O(n), alors f ∈ Θ(n).	FAUX. O(n) est une borne supérieure, la fonction pourrait être en O(1).
   Si f ∈ Θ(n), alors f ∈ O(n).	VRAI. Θ(n) = O(n) ∩ Ω(n).
   Soit un algorithme A avec une complexité temporelle en Θ(1), et P un programme implémentant l'algorithme A. Le temps d'exécution de P sur une machine donnée sera toujours identique, pour plusieurs exécutions de P.	FAUX. Le temps d'exécution dépend de beaucoup de facteurs, par exemple le nombre de processus concurrents sur la machine, l'état des différentes mémoires caches, les variabilité dans les entrées/sorties, etc.

2. Listes et tuples. L'appel {Nth L N} a une complexité temporelle en Θ(N) (si la liste L comporte au moins N éléments). En effet, le nombre d'opérations primitives est a (N-1) + b, pour certaines constantes a et b.

4. Boucles. La procédure Turlututu implémente deux boucles imbriquées avec les indices I et J. I prend les valeurs de 1 à N, et J va de I à N. On peut l'abstraire en

      pour I allant de 1 a N:
         pour J allant de I a N:
            afficher T.I
   

   L'élément T.1 est donc affiché N fois, T.2 l'est N-1 fois, ..., et T.N une fois.

   La procédure a une complexité temporelle Θ(n²), où n est la taille du tuple. En effet, le nombre de passages dans Loop2 est n + (n-1) + ... + 2 + 1 ∈ Θ(n²), et chaque passage effectue un nombre borné d'opérations primitives.

5. Création d'une liste. Pour construire une liste de n éléments, il faut un minimum de k.n opérations primitives, pour une certaine constante k. On ne peut pas en dire plus, car la construction de chaque élément de la liste pourrait être coûteuse. L'algorithme a donc une complexité en Ω(n). On ne peut pas donner de borne supérieure.

6. Tri par insertion.

   • La fonction Insert a une complexité temporelle O(n), où n est la longueur de la liste Ys. Le meilleur cas est celui où X est inférieur au premier élément de Ys, et on ne doit donc pas faire d'appel récursif. Sa complexité est Θ(1). Le pire cas est celui où l'on doit insérer X tout au bout de Ys ; sa complexité est Θ(n) parce qu'on doit parcourir toute la liste.

   • La fonction InsertList a une complexité O(n(n+m)), où n est la longueur de Xs et m celle de Ys. Le meilleur cas est celui où Xs est décroissante, dans ce cas l'insertion dans Ys se fait toujours en tête de Ys, et la complexité est Θ(n). Le pire est celui où Xs est déjà triée ; sa complexité est Θ(n(n+m)). Le terme n+m vient du fait que la longueur de Ys passe de m à n+m.

   • Pour la fonction InsertionSort, on utilise le résultat précédent. Comme la liste Ys est initialement vide, m=0 et la complexité est donc O(n²).

7. Recherche dichotomique.

   • Dans l'algorithme naïf, le meilleur (pire) cas est celui où X est le premier (dernier) élément de T. Les complexités respectives sont Θ(1) et Θ(n), où n est la taille de T. Un autre pire cas est lorsque X n'est pas dans T.

   • Avec une distribution uniforme, on va tester en moyenne la moitié des éléments de T. La complexité est donc Θ(n) en moyenne.

   • Comme la taille de la section considérée diminue de moitié à chaque appel récursif, l'algorithme de recherche dichotomique a une complexité en Θ(log n). Il n'y a ni meilleur ni pire cas.