Série TDTP.pdf

1. Complexité asymptotique (Notation Grand-O)

Pour déterminer la complexité asymptotique $O(f(n))$, on ne garde que le terme de plus haut degré et on ignore les constantes multiplicatives, soit la variable n.

• Algorithme A1 : $T_1(n)=9n²$
  • Le terme dominant est $n^2$.
  • Complexité : $O(n^2)$ (Quadratique)
• Algorithme A2 : $T_2(n) = 100n + 96$
  • Le terme dominant est n.
  • Complexité : $O(n)$ (Linéaire)

2. Quel algorithme a la meilleure complexité ?

L'algorithme A2 a la meilleure complexité asymptotique.

Raisonnement : La complexité linéaire $O(n)$ croît beaucoup moins vite que la complexité quadratique $O(n^2)$ lorsque n devient grand. Même si $A_2$ a de grandes constantes au début (100 et 96), $A_1$ finira inévitablement par devenir beaucoup plus lent.

3. Preuve des solutions (Recherche de $c$ et $n_0$)

La définition formelle de $T(n) = O(f(n))$ est :

$n \ge n_0$ Il existe des constantes positives $c$ et $n_0$ telles que $0 \le T(n) \le c \cdot f(n)$ pour tout .$0 \le T(n) \le c \cdot f(n)$:

Pour A1 ($T_1(n) = 9n^2$ est $O(n^2)$)

Nous cherchons $c$ et $n_0$ tels que :

$9n^2 \le c \cdot n^2$

Si nous choisissons $c = 9$, l'inégalité devient $9n^2 \le 9n^2$, ce qui est vrai pour tout $n \ge 1$.

• $c = 9$
• $n_0 = 1$

Pour A2 ( $T_2(n) = 100n + 96$ est $O(n)$)