Complexité des algorithmes

Complexité des algorithmes

Frédéric Herbreteau, Bordeaux INP/LaBRI (frederic.herbreteau@bordeaux-inp.fr)

Qu’est-ce que la complexité?

Algorithme:

Procédure de calcul bien définie qui prend en entrée une valeur, ou un ensemble de valeurs, et qui donne en sortie une valeur, ou un ensemble de valeurs. Un algorithme est donc une séquence d’étapes de calcul qui transforment l’entrée en sortie (Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, “Introduction à l’algorithmique”)

Complexité:

La complexité d’un algorithme est le nombre d’opérations élémentaires qu’il doit effectuer pour mener à bien un calcul en fonction de la taille des données d’entrée.

Taille des données d’entrée

  • La taille des données d’entrées dépend du codage de celles-ci.
  • On choisit taille = dimensions les plus significatives.

Exemple:

Entrée Dimensions significatives
éléments le nombre d’éléments
nombres nombre de bits nécessaire à l’encodage
polynômes degré + nombre de coeff. non nuls
matrices $m \times n$ $\max(m,n)$ ou $m \times n$ ou $m + n$
listes ou tableaux longueur ou nombre d’éléments

Temps de calcul

Le temps de calcul sur machine est très difficile à prévoir:

  • interprétation/compilation de programme haut niveau vers bas niveau
  • fort impact de l’environnement: système d’exploitation, multi-threading,…
  • optimisation dépendantes du contexte: caches, prédictions de branches,…

On considère un modèle d’ordinateur idéalisé RAM:

  • processeur unique
  • instructions exécutées séquentiellement
  • mémoire non bornée
  • accès aléatoires à la mémoire en temps constant

Complexités

  • Deux ressources requises par un algorithme:
    • complexité temporelle: temps de calcul
    • complexité spatiale: quantité de mémoire utilisée
  • Deux évaluations de la complexité:
    • évaluation pratique: mesure précise des ressources consommées sur une machine donnée
    • évaluation théorique: ordre de grandeur de ces coüts, évalué indépendamment d’un contexte précis d’exécution
  • Dans ce cours:
    • évaluation théorique de la complexité temporelle
    • objectif: dans quel contexte un algorithme est-il utilisable? Le plus adéquat?

Calcul de complexité

Temps de calcul des opérations fondamentales

Définition: la complexité d’un algorithme $\mathcal{A}$ sur entrée $x$ est le nombre d’opérations élémentaires réalisées lors de l’exécution de $\mathcal{A}$ sur $x$

Nous cherchons donc à caractériser ce nombre, en fonction de la taille $n$ de l’entrée

Définition: opération élémentaire = opération en temps constant (indépendant des entrées)

  • Opérations arithmétiques ($+$, $\times$, $<$, $=$, …) sur “petits nombres”
  • Accès mémoire élémentaires (lecture / écriture)
  • Sauts conditionnels et inconditionnels

Approche adoptée: chaque ligne $i$ coûte un temps constant $c_i$, on compte le nombre d’exécutions de chaque ligne

Exemple

1 def findZeroLinear(f: Function, a: float, b: float, eps: float) -> float | None:
2    x: float = a
3    while x <= b:
4        xx: float = min(b, x + eps)
5        if f(x) * f(xx) <= 0:
6            return x
7        x += eps
8    return None # pas de zéro trouvé

On note $c_i$ le coût de la ligne $i$ et $N_i$ son nombre d’exécutions

  • sortie en ligne 6: $T = c_2 + (c_3 + c_4 +c_5) \cdot N_{while} + c_6 + c_7 \cdot (N_{while} - 1)$
  • sortie en ligne 8: $T = c_2 + c_3 \cdot N_{while} + (c_4 + c_5 + c_7) \cdot (N_{while} - 1) + c_8$

Hypothèse simplificatrice: $f$ s’exécute en temps constant (négligeable)

Trois approches de la complexité

bg right:45% fit

  • Complexité au mieux
    • cas favorable, rare en pratique
  • Complexité au pire
    • cas défavorable, réaliste et pertinent pour obtenir une borne supérieure
  • Complexité en moyenne
    • moyenne des complexités, difficile à déterminer

Complexité “au mieux”

Définition: La complexité au mieux d’un algorithme $\mathcal{A}$ est $\min_{\mathcal{A}}(n) = \min \set{ T_{\mathcal{A}}(e) \, , \, e \in E_n}$ où $E_n$ est l’ensemble des entrées de taille $n$

On minimise sur toutes les entrées de même taille $n$

Exemple: dans le meilleur cas, findZeroLinear trouve un zéro dans le premier intervalle $[a; a+\epsilon]$. Sortie en ligne 6 avec $N_{while} = 1$ exécution de la boucle while Alors: \(\min_{findZeroLinear} = c_2 + c_3 + c_4 + c_5 + c_6\) La fonction findZeroLinear s’exécute en temps constant

Complexité “au pire”

Définition: La complexité au pire d’un algorithme $\mathcal{A}$ est $\max_{\mathcal{A}}(n) = \max \set{ T_{\mathcal{A}}(e) \, \vert \, e \in E_n}$ où $E_n$ est l’ensemble des entrées de taille $n$

On maximise sur toutes les entrées de même taille $n$

Exemple: dans le pire cas, findZeroLinear ne trouve pas de zéro dans $[a; b]$. Sortie en ligne 8 avec $N_{while} = \frac{1}{\epsilon} \cdot (b - a) + 1$ itérations de la boucle while Alors: \(\max_{findZeroLinear} = (c_3 + c_4 + c_5 + c_7) \cdot N_{while} + (c_2 - c_4 - c_5 -c_7 + c_8)\) Le temps de calcul est proportionnel à $\frac{1}{\epsilon} \cdot (b - a)$

La complexité au pire donne une borne supérieure pertinente sur le temps de calcul

Complexité “en moyenne”

Définition: La complexité en moyenne d’un algorithme $\mathcal{A}$ est $moy_{\mathcal{A}}(n) = \left(\sum_{e \in E_n} p_n(e) \cdot T_{\mathcal{A}}(e)\right)$ où:

  • $E_n$ est l’ensemble des entrées de taille $n$
  • et $p_n$ est une distribution de probabilités des données de taille $n$.

On calcule la moyenne des coûts sur les entrées de taille $n$

Déterminer une distribution $p_n$ représentative des entrées est généralement difficile

Exemple: quelle est la distribution des entrées de findZeroLinear?

Complexité asymptotique

Pourquoi évaluer la complexité des algorithmes?

Objectifs: comparer des algorithmes, choisir un algorithme adapté

  • importance de la vitesse de croissance de la complexité
  • les constantes sont négligeables pour des données assez grosses

Exemple: complexité au pire de findZeroLinear: \((c_3 + c_4 + c_5 + c_7) \cdot N_{while} + (c_2 - c_4 - c_5 -c_7 + c_8)\) $N_{while} = \frac{1}{\epsilon} \cdot (b - a)$ est le facteur dominant:

“Augmenter la précision $\epsilon$ d’un facteur 10, multiplie le temps de calcul par 10”

Approche: estimation des les complexités aux constantes près

Borne asymptotique supérieure

bg right:30% fit

Définition: $f$ est grand-$\Omicron$ de $g$, noté $f \in \Omicron(g)$, s’il existe une constante réelle $c > 0$ (facteur multiplicatif) et une constante entière $n_0 \in \mathbb{N}$ (seuil) telles que:

\[f(n) \le c \cdot g(n) \text{ pour tout } n \ge n_0\]

Exercice 1: Montrer que

  • $3n^4 - 2n^3 + 7n +1 \in \Omicron(n^4)$
  • $7n^2 + 10n \cdot \log(n) + 5 \in \Omicron(n^2)$
  • $7 \log(n) + 12 \in \Omicron(\log(n))$
  • $2^{2n + 3} \in \Omicron(2^n)$

Borne asymptotique inférieure

bg right:30% fit

Définition: $f$ est Omega de $g$, noté $f \in \Omega(g)$, s’il existe une constante réelle $c > 0$ (facteur multiplicatif) et une constante entière $n_0 \in \mathbb{N}$ (seuil) telles que:

\[f(n) \ge c \cdot g(n) \text{ pour tout } n \ge n_0\]

Exercice 2: Montrer que

  • $n^2 + 3n \in \Omega(10^6 \cdot n)$
  • $n \in \Omega(\log(n))$
  • $5n \not\in \Omega(10^{-6} \cdot n^2)$

Équivalence asymptotique

bg right:30% fit

Définition: $f$ est Théta de $g$, noté $f \in \Theta(g)$, s’il existe deux constantes réelles $c_1, c_2 > 0$ (facteurs multiplicatifs) et une constante entière $n_0 \in \mathbb{N}$ (seuil) telles que:

\[c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \text{ pour tout } n \ge n_0\]

Exercice 3: Montrer

  • $3n^2 -7n + 8 \in \Theta(n^2 +9n -3)$
  • $3n^3 \not\in \Theta(4n^2+5)$

Prépondérance asymptotique

Définition: $f$ est petit-$\omicron$ de $g$, noté $f \in \omicron(g)$, si pour toute constante $\varepsilon > 0$ (facteur multiplicatif), il existe une constante entière $n_0 \in \mathbb{N}$ (seuil) telle que: \(f(n) \le \varepsilon \cdot g(n) \text{ pour tout } n \ge n_0\) en d’autres termes: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$

Propriété: Si $f \in \omicron(g)$, alors $f \in \Omicron(g)$ et $g \notin \Omicron(f)$

Exemple:

  • $4n^2 + 3n \in \omicron(n^3)$
  • $\log_2(n) \in \omicron(n)$
  • $4n^5 - 2n^3 +8 \in \omicron(2^n)$

Comparaison asymptotique des complexités

bg right:50% fit

  • pour tout polynôme $f$ de degré $d$ on a $f \in \Theta(x^d)$
  • pour tous réels $a, b$ tels que $a > 1$, on a $n^b \in \omicron(a^n)$
  • pour tous réels $a, b > 0$, on a $(\ln n)^b \in \omicron(n^a)$

Comparaison des temps de calcul

En supposant $10^9$ opérations/seconde

n $\log_2(n)$ $n$ $n\cdot \log_2(n)$ $n^2$ $n^3$ $2^n$
$10^2$ 6ns 100ns 664ns 10 $\mu s$ 1ms $4 \cdot 10^{13}$ ans
$10^3$ 10ns 1 $\mu s$ 10 $\mu s$ 1ms 1s  
$10^4$ 13ns 10 $\mu s$ 132 $\mu s$ 0.1s 17min  
$10^5$ 16ns 100 $\mu s$ 1.66ms 10s 12 jours  
$10^6$ 20ns 1ms 20ms 17min 31 ans  
$10^7$ 23ns 10ms 0.23s 28h 30 millénaires  
$10^8$ 26ns 100ms 2.66s 4 mois    

Complexités fréquentes

Pour une entrée de taille $n$ et une constante $k > 1$:

Complexité Vitesse Formulation Exemple
Constante Le plus rapide $\Omicron(1)$ accès mémoire
Logarithmique Très rapide $\Omicron(\log(n))$ recherche dichotomique
Linéraire Rapide $\Omicron(n)$ recherche linéaire
Quasi-linéaire Assez rapide $\Omicron(n \cdot \log(n))$ tris (quicksort)
Polynômiale Moyen $\Omicron(n^k)$ tris par comparaison (tri bulle)
Exponentielle Lent $\Omicron(k^n)$ résolution du Rubik’s cube
Factorielle Très lent $\Omicron(n!)$ optimisation, trajet optimal (en $n^n$)

Analyse asymptotique

Évaluation asymptotique: instructions élémentaires et séquence

Instruction élémentaire

Par définition, execution en temps constant: $\Theta(1)$

Séquence

$I_1; I_2$ avec $I_1 \in \Omicron(f_1)$ et $I_2 \in \Omicron(f_2)$

Alors:

\[T \in \Omicron(f_1 + f_2)\]

De même pour $\Omega$ et $\Theta$.

Évaluation asymptotique: conditionnelle

if C:
    A
else:
    B

  • si $T_C \in \Omicron(f_C)$, $T_A \in \Omicron(f_A)$ et $T_B \in \Omicron(f_B)$, alors: \(T = \Omicron(f_C + \max(f_A, f_B))\)

  • si $T_C \in \Omega(f_C)$, $T_A \in \Omega(f_A)$ et $T_B \in \Omega(f_B)$, alors: \(T = \Omega(f_C + \min(f_A, f_B))\)

Évaluation asymptotique: boucles bornées

for i in range(j, k):
    Ai
  • Si $T_{A_i} \in \Omicron(f_i)$ alors:
\[T \in \Omicron\left(\sum_{i=j}^{k-1} f_i\right)\]
  • Si $T_{A_i}$ est constant et égal à $\Omicron(f)$ alors: $T \in \Omicron\left((k-j) \cdot f\right)$
  • Si $T_{A_i} \in \Omicron(i^c)$ pour une constante $c \in \mathbb{N}$, alors: $T \in \Omicron(n^{c+1})$

De même pour $\Omega$ et $\Theta$.

Évaluation asymptotique: boucles non bornées

while C:
    A
  • Si $T_{A_i} \in \Omicron(f_i)$ et $T_C \in \Omicron(f_C)$ et $N$ itérations, alors:
\[T \in \Omicron\left(\left(\sum_{i=1}^{N} f_i\right) + (N+1) \cdot f_C \right)\]
  • Si $T_{A_i}$ est constant et égal à $\Omicron(f)$ alors: $T \in \Omicron\left(N \cdot f + (N+1) \cdot f_C\right)$

De même pour $\Omega$ et $\Theta$.

Exemple

1 def findZeroLinear(f: Function, a: float, b: float, eps: float) -> float | None:
2    x: float = a
3    while x <= b:
4        xx: float = min(b, x + eps)
5        if f(x) * f(xx) <= 0:
6            return x
7        x += eps
8    return None # pas de zéro trouvé

On compose les complexités asymptotiques de chaque ligne selon les instructions.

Exemple: Les opérations élémentaires sont $\Omicron(1)$, et $N_{while} = \frac{1}{\epsilon} \cdot (b-a) + 1$ itérations Alors: $T_{FindZeroLinear} = \Omicron\left(\frac{1}{\epsilon} \cdot (b - a)\right)$

Hypothèse simplificatrice: $f$ s’exécute en temps constant (négligeable)

Conclusion

  • La complexité algorithmique ne porte pas sur le temps de calcul, mais sur la vitesse à laquelle il augmente avec les entrées
  • L’évaluation asymptotique permet de:
    • comparer des algorithmes de complexités différentes
    • choisir un algorithme adéquat pour un problème donné
  • La complexité asymptotique ne permet pas de comparer des algorithmes de même complexité: $\Omicron(n) = \Omicron(10n+3) = \Omicron(10^6.n)$
  • La complexité asymptotique parle des grandes valeurs de $n$
    • $n^{100} \in \Omicron(2^n)$, mais pour $2^n < n^{100}$ pour $n < 997$
  • Une machine standard plus puissante ($\times 100$, $\times 1000$,…) ne change pas la classe de complexité d’un algorithme: $\Theta(log(n)) \neq \Theta(n) \neq \Theta(2^n)$

Exercices

Exercice 4

Pourquoi findZeroLinear n’est-elle pas $\Theta\left(\frac{1}{\epsilon} \cdot (b - a)\right)$?

Execice 5

Soient deux algorithmes $\mathcal{A}$ et $\mathcal{B}$ qui résolvent le même problème. Le premier est de complexité $10n$ et le second $n^2$. Quel est le plus efficace?

Exercice 6

  • Montrer que si $f \in \Omicron(g)$, alors pour tout $k \ge 0$, $k \cdot f \in \Omicron(g)$
  • En déduire que pour toutes constantes $a, b > 0$: $a^b \in \Omicron(1)$ et $a^{x+b} \in \Omicron(a^x)$ pour tout $x \ge 1$

Exercice 7

Quelle est la complexité au pire des algorithmes ci-dessous?

  • $\mathcal{A}_1$
for i in range(n):
    for j in range(n):
        x = x + 1
  • $\mathcal{A}_2$
for i in range(n):
    for j in range(n):
        for k in range(n):
            x = x + 1

Rappel: range(i, j) est l’intervalle $[i; j-1]$, et range(n) est range(0, n)

Exercice 8

Quelle est la complexité au pire des algorithmes suivants?

  • $\mathcal{A}_3$
for i in range(n):
    for j in range(i):
        x = x + 1
  • $\mathcal{A}_4$
for i in range(n):
    for j in range(i):
        for k in range(j):
            x = x + 1

Exercice 9

Quelle est la complexité au pire de ces algorithmes?

  • $\mathcal{A}_5$
for (i = n; i > 1; i = i / 2)
    for (j = 0; j < i; i = i + 1)
        x = x + 1
  • $\mathcal{A}_6$:
for (i = 5; i <= n-5; i = i + 1)
    for (j = i-5; j <= i+5; j = j + 1)
        x = x + 1

Exercice 10

Quelle est la complexité au pire, au mieux et en moyenne de l’algorithme ci-dessous?

  • $\mathcal{A}_7$:
if a > b:
    for i in range(n):
        x = x + 1
else:
    x = x + 2

On considèrera que $a$ et $b$ sont des entiers de valeur maximale $M$.