Introduction à la complexité

Introduction à la complexité

Lors de la résolution de problèmes algorithmiques, il est souvent utile d'avoir une idée de la complexité des algorithmes qu'on écrit. On distingue deux complexités:

  • La complexité temporelle, qui donne une mesure du temps d'exécution d'un algorithme
  • La complexité spatiale, qui donne une mesure de la quantité de mémoire utilisée par un algorithme.

Notation O de Landau

Si $$\exists C>0, \exists N\in\mathbb N\forall n\geq N, |f(n)|\leq C|g(n)|$$ alors on écrira $f(n)=O(g(n))$. En français, $f$ est dominée par $g$ si à partir d'un certain rang $N$, on a $-C\cdot g(n)\leq f(n)\leq C \cdot g(n)$ pour une certaine constante $C$.

Ce la permet de comparer une fonction à des échelles de référence

  • Les fonctions constantes
  • Les fonctions logarithmiques (proportionnelles à un logarithme d'un polynôme en $n$). On dit parfois qu'elles sont quasi-constantes, puisque le logarithme a une croissance très lente.
  • Les fonctions polynomiales (de la forme $a + a_1n + a_2n^2+\cdots +a_k n ^ k$)
  • Les fonctions exponentielles (proportionnelles à $a^n$ avec $a$ positif)

Complexité temporelle

Pour donner une complexité temporelle d'un algorithme, il faut d'abord s'accorder sur le type d'opérations que l'on choisit pour mesurer le temps d'exécution. La plupart du temps, on choisit de compter les assignations et les opérations élémentaires. On supposera que ces opérations s'effectuent en temps constant, c'est à dire que le temps d'exécution ne varie pas en fonction de la taille des éléments manipulés (par exemple on supposera que calculer $1000\times 1000$ prend autant de temps que $3\times 5$, ce qui est une hypothèse raisonnable pour un ordinateur).

Supposons que l'on propose une fonction $f$ de paramètres $(a_1, \cdots, a_p)$ dont on souhaite évaluer la complexité temporelle. On note par exemple $\Gamma(a_1, \cdots, a_p)$ le nombre d'opérations effectuées par la fonction $f$ lorsqu'on lui fourni l'entrée $(a_1, \cdots, a_p)$. Lorsqu'on cherche une complexité temporelle, on cherche une majoration du nombre d'opérations (c'est à dire qu'on cherche un nombre d'opérations qui ne sera jamais excédé).

On se donne alors $n_1, \cdots, n_p$ des nombres qui dépendent respectivement de $a_1, \cdots, a_n$ qui représentent la taille des arguments donnés à la fonction $f$. On étudie alors le pire cas pour les entrées de tailles $n_1, \cdots, n_p$ (par exemple, on va considérer que toutes les boucles effectuent un maximum d'itérations). On note $C(n_1, \cdots, n_p)$ le nombre d'opérations effectuées dans le pire cas. On peut alors affirmer $$\Gamma(a_1, \cdots, a_p)\leq C(n_1, \cdots, n_p)$$

La fonction $C(n_1, \cdots, n_p)$ est la complexité temporelle. Très souvent, on ne peut pas donner d'expression explicite de $C$. On va donc chercher à comparer cette valeur à des échelles de référence.

La plupart du temps, on se donne $n = n_1 + \cdots + n_p$ (ou une autre fonction faisant intervenir $n_1, \cdots, n_p$) qui mesure la taille totale de l'entrée. Ainsi, on peut simplement écrire la complexité $C(n)$.

Calcul avec les notations de Landau

Lorsque que l'on fait une comparaison asymptotique (c'est à dire que l'on écrit $f(n)=O(g(n))$, la constante $C$ qui apparaît n'a aucune importance. On ne cherche qu'à comparer les vitesse de croissance, les constantes multiplicatives n'ont pas d'importance. Ainsi, si $K$ est une constance, alors $$O(K g(n)) = O(g(n))$$

Ensuite, on garde toujours le morceau qui a la croissance la plus élevée (pour plus de rigueur on devrait parler d'équivalents): $$O(n^4 + 2n ^ 2 + n) = O(n^4)$$ $$O((n ^3 + n) ln (2n ^2)) = O(n ^3ln(n))$$

Quelques exemples

def f(n):
    s = 0
    for i in range(n):
        s += i
    return s

Ici, la complexité est $O(n)$: on fait $n$ fois une addition. Cela veut dire qu'on peut s'attendre à ce que $f(1000)$ prennent environ $100$ fois plus de temps à s’exécuter que $f(10)$. On voit au passage que l'optimisation ne se résume pas à modifier une constante multiplicative (c'est à dire combiner plusieurs opérations en temps constant en une seule), mais elle passe aussi parfois par une réécriture complète de l'algorithme: la fonction suivante est mathématiquement équivalente (elle donne les mêmes résultats), mais s'exécute en temps constant

def f(n):
    return n * (n-1) / 2