Complexité algorithmique

Motivation

L'analyse de la complexité permet de comparer l'efficacité des algorithmes indépendamment de la machine utilisée. On distingue :

• Complexité en temps : nombre d'opérations élémentaires en fonction de la taille de l'entrée
• Complexité en espace : quantité de mémoire utilisée

Notation de Landau

Définition. Soit $f, g : \mathbb{N} \to \mathbb{R}^+$. On écrit $f(n) = O(g(n))$ s'il existe $C > 0$ et $n_0 \in \mathbb{N}$ tels que :

$$\forall n \geq n_0, \quad f(n) \leq C \cdot g(n)$$

On utilise aussi :

• $f(n) = \Omega(g(n))$ si $g(n) = O(f(n))$
• $f(n) = \Theta(g(n))$ si $f(n) = O(g(n))$ et $f(n) = \Omega(g(n))$

Classes de complexité courantes

| Complexité | Nom | Exemple | |-----------|-----|---------| | $O(1)$ | Constante | Accès à un élément de liste par indice | | $O(\log n)$ | Logarithmique | Recherche dichotomique | | $O(n)$ | Linéaire | Parcours d'une liste | | $O(n \log n)$ | Quasi-linéaire | Tri fusion | | $O(n^2)$ | Quadratique | Tri par insertion (pire cas) | | $O(2^n)$ | Exponentielle | Sous-ensembles d'un ensemble |

Complexité dans le meilleur et le pire cas

Pour un algorithme donné, on distingue :

• Complexité dans le pire cas $C_{\text{pire}}(n)$ : le maximum sur toutes les entrées de taille $n$
• Complexité dans le meilleur cas $C_{\text{meilleur}}(n)$ : le minimum
• Complexité en moyenne $C_{\text{moy}}(n)$ : la moyenne sur toutes les entrées (avec une distribution de probabilité)

En CPGE, on s'intéresse le plus souvent à la complexité dans le pire cas.

Preuve de terminaison : le variant de boucle

Définition. Un variant de boucle est une quantité entière, positive, qui décroît strictement à chaque itération. Son existence prouve que la boucle termine.

Exemple : dans la recherche dichotomique, le variant est $d - g$ (différence entre les bornes droite et gauche).

Preuve de correction : l'invariant de boucle

Définition. Un invariant de boucle est une propriété qui est vraie avant la boucle, et qui reste vraie après chaque itération.

Exemple : pour le calcul de $n!$ par une boucle :

```python def factorielle(n): r = 1 for i in range(1, n + 1): r = r * i # Invariant : à l'entrée du tour i, r = (i-1)! return r ```

L'invariant est : au début de l'itération $i$, on a $r = (i-1)!$. Après la dernière itération ($i = n$), on obtient $r = n!$.