TD 03 - Complexité et analyse asymptotique

1 Complexités min et max

1.1 Exercice 1

On cherche si un nombre \(e\) se trouve dans un tableau de \(n\) éléments. On décide de parcourir le tableau dans l’ordre des indices.

Déterminez la complexité dans le meilleur et dans le pire des cas.

1.2 Exercice 2 🏠

Un tableau d’entiers contient \(n\) éléments. On veut savoir si tous les éléments de ce tableau sont différents deux à deux.

Déterminez la complexité minimale et la complexité maximale (en nombre de comparaisons) de l’algorithme résolvant ce problème.

1.3 Exercice 3

On dispose d’un tableau trié de \(n\) éléments tous distincts. On souhaite déterminer si l’entier \(e\) appartient au tableau en utilisant cette méthode :

  • On coupe notre tableau en deux parties égales (ou presque)
  • Si la valeur de l’élément où on a coupé le tableau est égale à \(e\), c’est fini
  • Si la valeur de l’élément où on a coupé le tableau est inférieure à \(e\), on recommence avec la partie droite du tableau
  • Sinon on recommence avec la partie gauche du tableau

Déterminez la complexité minimale et la complexité maximale (en nombre de découpes de tableau) de l’algorithme résolvant ce problème.

2 Manipulations des notations asymptotiques

2.1 Exercice 4

Un algorithme met 1 seconde pour traiter un tableau de 1 000 éléments sur votre ordinateur personnel. Quel temps lui faudra-t-il pour traiter 100 000 éléments si :

  1. son temps d’exécution est à peu près proportionnel à \(n\) ?
  2. son temps d’exécution est à peu près proportionnel à \(\sqrt{n}\) ?
  3. son temps d’exécution est à peu près proportionnel à \(n^2\) ?
  4. son temps d’exécution est à peu près proportionnel \(n\log(n)\) ?

2.2 Exercice 5 🏠

On suppose disposer d’une machine capable d’effectuer \(2^{32}\) opérations par seconde. On considère des algorithmes dont les complexités asymptotiques sont les suivantes: \(\Theta(\log_2(n))\), \(\Theta(n)\), \(\Theta(n^2)\) et \(\Theta(2^{n})\).

Pour chaque complexité, donner la taille des problèmes que l’on peut résoudre en une seconde.

2.3 Exercice 6

Pour chaque paire de fonctions \(f\) et \(g\), dire si \(f=O(g)\), \(f=\Omega(g)\) et \(f=\Theta(g)\) (en justifiant).

  1. \(f(n)=n+1;~g(n)=2n^2+n\)
  2. \(f(n)=100n^2;~g(n)=0.01n^3\)
  3. \(f(n) = \log(n^5);~ g(n) = \log(\sqrt{n})\)
  4. \(f(n)=(\log(n))^{10};~g(n)=\sqrt{n}\)
  5. \(f(n)=2^n;~g(n)=2^{n+1}\)
  6. \(f(n)=2^{n};~g(n)=2^{2n}\)
  7. 🏠 À faire à la maison : \(f(n) = 2^n;~ g(n) = 2^{\frac{n}{2}}\)
  8. 🏠 À faire à la maison : \(f(n)=\frac{n}{\log(n)};~g(n)=\log^2(n)\)
  9. 🏠 À faire à la maison : \(f(n)=n!;~g(n)=(n+1)!\)
  10. 🏠 À faire à la maison : \(f(n) = (n+2)!;~ g(n) = n^2(n-1)!\)
  11. 🏠 À faire à la maison : \(f(n) = 2n+(2n-1)+\dots+(n+1);~ g(n) = n+(n-1)+\dots+1\)
  12. 🏠 À faire à la maison : \(f(n) = 2^n+2^{n-1}+\dots+2+1;~ g(n) = 2^{n/2}\)

3 Analyse asymptotique

3.1 Exercice 7

Donner la complexité asymptotique de chaque algorithme en fonction de \(n\). On rappelle que le symbole mathématique \(|\) signifie divise.

BOUCLE 1
DEBUT
  i ← 1
  TQ i ≤ n FAIRE
    j ← 1
    TQ j ≤ i FAIRE
      k ← 1
      TQ k ≤ 2^j FAIRE
        k ← k+1
      FTQ
      j ← j+1
    FTQ
    i ← i+1
  FTQ
FIN
BOUCLE 2
DEBUT
  i ← n
  TQ 1 < i FAIRE
    j ← 1
    TQ j < n FAIRE
      j ← j+1
    FTQ
    i ← ⌊i/2⌋
  FTQ
FIN
BOUCLE 3
DEBUT
  i ← 1
  TQ i ≤ n FAIRE
    j ← 1
    TQ j ≤ n FAIRE
      k ← 1000
      TQ k ≥ 1 FAIRE
        k ← ⌊k/2⌋
      FTQ
      j ← j+2
    FTQ
    i ← i+1
  FTQ
FIN
BOUCLE 4
DEBUT
  i ← 1
  TQ i ≤ n FAIRE
    j ← 1
    TQ j ≤ n FAIRE
      SI 2|j ALORS
        k ← 1
        TQ k ≤ j FAIRE
          k ← k+1
        FTQ
      FSI
      j ← j+1
    FTQ
    i ← i+1
  FTQ
FIN
BOUCLE 5
DEBUT
  i ← 1
  j ← n
  TQ i ≤ j FAIRE
    i ← i+1
    j ← j-1
  FTQ
FIN
ImportantRappel : Notations asymptotiques
  • \(O(g)\) (grand-O) : Borne supérieure asymptotique. \(f = O(g)\) signifie que \(f\) croît au plus aussi vite que \(g\)
  • \(\Omega(g)\) (grand-Omega) : Borne inférieure asymptotique. \(f = \Omega(g)\) signifie que \(f\) croît au moins aussi vite que \(g\)
  • \(\Theta(g)\) (grand-Theta) : Équivalence asymptotique. \(f = \Theta(g)\) signifie que \(f = O(g)\) ET \(f = \Omega(g)\)

4 Classes de complexité courantes

De la plus rapide à la plus lente :

\(O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)\)