%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Optimisation de problème/Optimisation de problème|Accueil · Optimisation de problème]]
>
> | | [[Code et Développement/Programmation/Optimisation de problème/02_Le problème du sac à dos\|Le problème du sac à dos →]] |
> |:---|---:|
%% nav-fin %%
# Complexité algorithmique
Ce chapitre présente la complexité algorithmique.
L'objectif est de savoir estimer si un algorithme donne sa réponse en un temps raisonnable.
## Complexité en temps
La complexité d'un algorithme mesure les ressources qu'il utilise pour résoudre un problème.
Ces ressources dépendent de la taille des données d'entrée, notée *n*.
On distingue la complexité en temps d'exécution et la complexité en espace, c'est-à-dire en mémoire utilisée.
Ce chapitre traite de la complexité en temps.
Elle s'estime en comptant les opérations élémentaires réalisées par l'algorithme : affectations, opérations arithmétiques et logiques, évaluations de conditions.
Le processeur exécute ces opérations. Un processeur cadencé à 3 GHz en effectue environ 3 milliards par seconde.
Le temps d'exécution dépend donc de *n* et de l'ordinateur utilisé.
## Meilleur cas, cas moyen, pire cas
On étudie trois cas : le meilleur cas, le cas moyen et le pire cas.
Exemple : on cherche si une valeur est présente dans une liste de *n* éléments.
```python
def recherche(x, l):
"""Renvoie True si x est un élément de la liste l."""
for element in l:
if element == x:
return True
return False
nombres = [5, 8, 1, 4, 2] # n = 5
print(recherche(5, nombres)) # True après 1 comparaison
print(recherche(1, nombres)) # True après 3 comparaisons
print(recherche(2, nombres)) # True après 5 comparaisons
```
- Meilleur cas : la valeur cherchée est la première de la liste, ici 5. Une comparaison suffit.
- Cas moyen : la valeur cherchée est en moyenne au milieu de la liste. Il faut environ *n*/2 comparaisons. Ici, chercher 1 demande 3 comparaisons.
- Pire cas : la valeur cherchée est la dernière de la liste, ici 2, ou elle est absente. Il faut *n* comparaisons.
**À manipuler :** choisissez la valeur cherchée et comptez les comparaisons.
```sq-recherche
liste: 5, 8, 1, 4, 2
valeur: 2
mode: séquentielle
```
## La notation O
La complexité d'un algorithme s'exprime en général pour le pire cas.
On la note avec un « grand O ».
La recherche ci-dessus demande *n* comparaisons dans le pire cas. Sa complexité est *O(n)*, on dit « de l'ordre de *n* ».
Les complexités les plus courantes sont les suivantes.
| Notation | Nom | Exemple |
|---|---|---|
| *O(1)* | constante | tester si un nombre est pair |
| *O(log n)* | logarithmique | recherche dichotomique |
| *O(n)* | linéaire | recherche séquentielle |
| *O(n log n)* | quasi linéaire | tri fusion |
| *O(n²)* | quadratique | tri par insertion |
| *O(2ⁿ)* | exponentielle | examen de toutes les parties d'un ensemble |
**À manipuler :** faites varier *n* et comparez le nombre d'opérations et le temps estimé.
```sq-croissance
n: 20
```
## Exemples d'algorithmes
### Tester si un nombre est pair
```python
def pair(x):
"""Renvoie True si x est pair."""
return x % 2 == 0
print(pair(7)) # False
print(pair(8)) # True
```
La fonction `pair` réalise une seule opération, quelle que soit la valeur de *x*.
Elle s'exécute en temps constant. Sa complexité est *O(1)*.
### Recherche dichotomique
La recherche dichotomique cherche une valeur dans une liste **triée**.
Elle compare la valeur cherchée à l'élément du milieu de la liste.
Si ce n'est pas la bonne valeur, elle poursuit la recherche dans la moitié qui peut la contenir.
Elle s'arrête quand la valeur est trouvée ou quand il ne reste plus d'élément à examiner.
```python
def recherche_dichotomique(x, l, debut=0, fin=None):
"""Renvoie True si x est présent dans l, liste triée en ordre croissant."""
if fin is None:
fin = len(l) - 1
if debut > fin:
return False
milieu = (debut + fin) // 2
if l[milieu] == x:
return True
elif x > l[milieu]:
return recherche_dichotomique(x, l, milieu + 1, fin)
else:
return recherche_dichotomique(x, l, debut, milieu - 1)
print(recherche_dichotomique(11, [1, 4, 5, 5, 7, 8, 11, 14, 14, 19])) # True
```
La fonction est récursive. Les paramètres `debut` et `fin` délimitent la partie de la liste encore à examiner.
Une version qui découpe la liste avec `l[milieu + 1:]` crée une copie à chaque appel. Cette copie coûte *O(n)* et fait perdre l'avantage de la méthode.
Calcul du nombre d'étapes *k* dans le pire cas :
- chaque appel divise par 2 la taille de la partie examinée ;
- après *k* appels, il reste *n*/2ᵏ éléments ;
- la recherche continue tant qu'il reste au moins un élément : 1 ≤ *n*/2ᵏ, soit 2ᵏ ≤ *n* ;
- donc *k* ≤ log₂(*n*).
La recherche dichotomique s'exécute en temps logarithmique. Sa complexité est *O(log n)*.
### Recherche séquentielle
```python
def recherche_sequentielle(x, l):
"""Renvoie True si x est présent dans l."""
for element in l:
if element == x:
return True
return False
print(recherche_sequentielle(12, [1, 4, 5, 5, 7, 8, 11, 14, 14, 19])) # False
```
Dans le pire cas, la recherche séquentielle parcourt les *n* éléments de la liste.
Elle s'exécute en temps linéaire. Sa complexité est *O(n)*.
**À manipuler :** comparez les deux recherches sur la même liste triée.
```sq-recherche
liste: 1, 4, 5, 5, 7, 8, 11, 14, 14, 19
valeur: 11
mode: comparaison
```
### Tri par insertion
Le tri par insertion range les éléments d'une liste en ordre croissant.
Il traite les éléments un par un et insère chacun à sa place parmi les éléments déjà triés.
Il est efficace seulement sur des listes de petite taille.
```python
def tri_insertion(l):
"""Trie la liste l en ordre croissant et affiche chaque étape."""
for i in range(1, len(l)):
x = l[i]
j = i
while j > 0 and l[j - 1] > x:
print("On décale", l[j - 1], "d'une case vers la droite")
l[j] = l[j - 1]
j -= 1
l[j] = x
print(l)
return l
tri_insertion([5, 4, 3, 2, 1])
```
Le pire cas est une liste triée en ordre décroissant, comme `[5, 4, 3, 2, 1]`.
**À manipuler :** suivez le tri du pire cas et comptez les décalages.
```sq-tri
algorithme: insertion
liste: 5, 4, 3, 2, 1
```
Calcul du nombre de décalages dans le pire cas :
- le premier élément demande 0 décalage ;
- le deuxième demande 1 décalage ;
- le troisième demande 2 décalages ;
- le dernier demande *n* − 1 décalages.
Le total est S = 0 + 1 + 2 + … + (*n* − 1).
On écrit la même somme dans l'ordre inverse : S = (*n* − 1) + (*n* − 2) + … + 1 + 0.
En additionnant terme à terme, chacun des *n* couples vaut *n* − 1 : 2S = *n*(*n* − 1).
Donc S = *n*(*n* − 1)/2 = *n*²/2 − *n*/2.
Pour *n* = 5, on obtient 5 × 4 / 2 = 10 décalages.
Le terme dominant est *n*²/2. Le tri par insertion s'exécute en temps quadratique. Sa complexité est *O(n²)*.
### Récapitulatif
| Algorithme | Pire cas | Complexité |
|---|---|---|
| Tester si un nombre est pair | 1 opération | *O(1)* |
| Recherche dichotomique | ⌊log₂(*n*)⌋ + 1 comparaisons | *O(log n)* |
| Recherche séquentielle | *n* comparaisons | *O(n)* |
| Tri par insertion | *n*(*n* − 1)/2 décalages | *O(n²)* |
## Temps d'exécution
Les quatre fonctions suivantes ont des complexités constante, linéaire, quadratique et exponentielle.
```python
def constant(n):
x = 1
def lineaire(n):
for i in range(n):
x = 1
def quadratique(n):
for i in range(n):
for j in range(n):
x = 1
def exponentiel(n):
for i in range(2 ** n):
x = 1
```
Le module `time` mesure leur durée réelle : `debut = time.time()`, puis l'appel, puis `time.time() - debut`.
La durée mesurée dépend de l'ordinateur. L'ordre de grandeur dépend de la complexité.
Sur un ordinateur portable, `lineaire(10**8)` et `quadratique(10**4)` réalisent chacune 10⁸ tours de boucle et durent quelques secondes.
`exponentiel(25)` réalise 2²⁵, soit environ 3,4 × 10⁷ tours. Chaque valeur de *n* supplémentaire double cette durée.
Le composant « Nombre d'opérations selon la complexité » ci-dessus donne ces ordres de grandeur sans exécuter de code.
## Problèmes d'optimisation
Un problème d'optimisation cherche la meilleure solution parmi toutes les solutions possibles.
Exemple : une caisse automatique doit rendre la monnaie avec le moins de pièces et de billets possible.
Les valeurs disponibles sont 1, 2, 5, 10, 20, 50 et 100 euros, en quantité illimitée.
```python
pieces = [1, 2, 5, 10, 20, 50, 100]
```
Un client paie un achat de 38 euros avec un billet de 100 euros. La caisse doit rendre 62 euros.
### 1. La force brute
La force brute génère toutes les combinaisons de pièces et de billets qui donnent 62 euros.
Elle garde ensuite la combinaison qui utilise le moins d'éléments.
Elle trouve toujours la solution optimale.
Le nombre de combinaisons croît de façon exponentielle avec la somme à rendre. La force brute ne convient qu'aux petites entrées.
### 2. L'algorithme glouton
Un algorithme glouton choisit à chaque étape la meilleure option locale, sans revenir sur ses choix.
Pour le rendu de monnaie, il rend à chaque étape la plus grande valeur inférieure ou égale au reste à rendre.
Il s'arrête quand le reste vaut 0.
```python
def rendu_glouton(pieces, r):
"""Renvoie la liste rendue par la méthode gloutonne, ou None si elle échoue."""
rendu = []
for p in sorted(pieces, reverse=True):
while p <= r:
rendu.append(p)
r -= p
if r > 0:
return None
return rendu
print(rendu_glouton([1, 2, 5, 10, 20, 50, 100], 62)) # [50, 10, 2]
```
Avec toutes les valeurs, le glouton rend 50 + 10 + 2, soit 3 éléments. C'est la solution optimale.
Le glouton ne donne pas toujours la solution optimale.
Sans billets de 5 et de 10 euros, il rend 50 + 2 + 2 + 2 + 2 + 2 + 2, soit 7 éléments.
La solution optimale est 20 + 20 + 20 + 2, soit 4 éléments.
**À manipuler :** retirez les valeurs 5 et 10, puis suivez le glouton jusqu'au bout.
```sq-monnaie
pièces: 1, 2, 5, 10, 20, 50, 100
montant: 62
```
Le glouton peut aussi ne trouver aucune solution.
Sans pièce de 1 euro, pour rendre 8 euros, il rend 5, puis 2. Il reste 1 euro, et aucune valeur disponible ne convient.
La solution existait pourtant : 4 pièces de 2 euros.
La fonction `rendu_glouton` ci-dessus renvoie `None` dans ce cas. Une version qui répète la boucle tant que le reste est positif ne s'arrête jamais.
**À manipuler :** suivez le glouton sur 8 euros sans pièce de 1 euro.
```sq-monnaie
pièces: 2, 5, 10, 20, 50, 100
montant: 8
```
### 3. La programmation dynamique
La programmation dynamique découpe le problème en sous-problèmes.
Elle les résout du plus petit au plus grand et conserve chaque résultat intermédiaire.
Pour le rendu de monnaie, elle calcule la meilleure façon de rendre 1 euro, puis 2 euros, et ainsi de suite jusqu'à la somme demandée.
Chaque résultat se déduit des résultats déjà calculés pour les sommes plus petites.
```python
def rendu_optimal(pieces, r):
"""Renvoie une liste de pièces de longueur minimale dont la somme vaut r, ou None."""
meilleur = [[]] + [None] * r # meilleur[s] : meilleure façon de rendre s
for s in range(1, r + 1):
for p in pieces:
if p <= s and meilleur[s - p] is not None:
if meilleur[s] is None or len(meilleur[s - p]) + 1 < len(meilleur[s]):
meilleur[s] = meilleur[s - p] + [p]
return meilleur[r]
print(rendu_optimal([1, 2, 20, 50, 100], 62)) # [20, 20, 20, 2]
print(rendu_optimal([2, 5, 10, 20, 50, 100], 8)) # [2, 2, 2, 2]
```
Cette fonction réalise environ *r* × *k* opérations, où *k* est le nombre de valeurs disponibles.
### Quelle méthode choisir ?
Le choix dépend du problème.
- La force brute donne la solution optimale, mais seulement sur de petites entrées.
- Un algorithme glouton est rapide. Il donne la solution optimale pour certains problèmes et des solutions médiocres pour d'autres.
- La programmation dynamique donne la solution optimale quand le problème se découpe en sous-problèmes qui se recouvrent.
## Classes P et NP
Les classes P et NP concernent les problèmes de décision, c'est-à-dire les problèmes dont la réponse est oui ou non.
Exemple de problème de décision : « la valeur *x* est-elle présente dans la liste *l* ? »
- **P** regroupe les problèmes de décision résolus par un algorithme en temps polynomial, par exemple en *O(n)* ou en *O(n²)*.
- **NP** regroupe les problèmes de décision dont une solution proposée se vérifie en temps polynomial.
- Tout problème de P appartient à NP.
- Un problème **NP-complet** appartient à NP, et tout problème de NP se ramène à lui en temps polynomial.
Aucun algorithme en temps polynomial n'est connu pour un problème NP-complet.
La question « P = NP ? » n'est pas résolue.
Les recherches présentées dans ce chapitre sont des problèmes de P.
Le tri n'est pas un problème de décision. Il sert ici d'exemple de calcul de complexité.
Les chapitres suivants présentent deux problèmes NP-complets : le [[Code et Développement/Programmation/Optimisation de problème/02_Le problème du sac à dos|problème du sac à dos]] et la [[Code et Développement/Programmation/Optimisation de problème/03_Satisfaisabilité (SAT)|satisfaisabilité]].
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Optimisation de problème/Optimisation de problème|Accueil · Optimisation de problème]]
>
> | | [[Code et Développement/Programmation/Optimisation de problème/02_Le problème du sac à dos\|Le problème du sac à dos →]] |
> |:---|---:|
%% nav-fin %%