Algorithmique — Complexité d'un algorithme

I. Généralités

1. Introduction

Bien que généralement associée à l'informatique, la notion d'algorithme vient de la déformation orale du nom d'un mathématicien arabe (persan) du 9^e siècle : Al-Khwârizmî. La notion d'algorithme est donc très ancienne et bien antérieure à la création du premier ordinateur ; elle est à lier à la notion de méthode de calcul.

Définition — Algorithme :

Un algorithme est une suite finie de calculs (ou d'instructions élémentaires), exécutés dans un ordre déterminé, qui permettent de résoudre un problème.

L'ordre dans lequel nous allons définir ces « opérations élémentaires » va donc avoir son importance. On considèrera qu'une opération élémentaire est une action simple, qui doit être facilement compréhensible pour la personne chargée d'effectuer cette action.

Schéma d'un algorithme : entrées → suite finie de calculs → sorties

Un algorithme prend en entrée des données et fournit un résultat en sortie. La valeur de sortie n'est pas obligatoirement du même type que la valeur d'entrée.

2. Pseudo-langage

Pour pouvoir décrire des algorithmes, on a besoin d'un langage formel minimum, sans être gêné par les détails syntaxiques des différents langages de programmation. On utilise alors ce qu'on appelle un pseudo-langage (ou pseudo-code). Ce langage est inspiré d'un langage de programmation tout en restant relativement proche du langage naturel. Il n'est pas exécuté par une machine, ce qui autorise quelques libertés de notation.

Comme notre langage de programmation est Python, les algorithmes dans ce cours seront parfois écrits en pseudo-langage, parfois directement en Python.

Exemple :

#En pseudo-langage :
Variables :       #déclaration des variables utilisées et de leur type
  n  entier
  x  flottant
  y  flottant

Debut
  y ← 1          #signe d'affectation : on affecte la valeur 1 à la variable y
  Pour (i de 1 à n) {    #début de la boucle
      y ← y + x
  }              #fin de la boucle
Fin

Ce qui est équivalent en Python à :

y = 1
for i in range(1, n + 1):
    y = y + x

II. Notion de complexité d'un algorithme

Dans cette partie, nous allons aborder la notion de complexité. C'est une notion très mathématique de l'informatique qui utilise des outils qui ne sont pas tous au programme de 1^re en mathématiques. Ce que nous allons voir n'est donc qu'une approche de ces notions.

Définition — Complexité algorithmique :

Les calculs de complexité d'un algorithme permettent d'évaluer la quantité de ressources (en temps et en mémoire) dont a besoin un algorithme pour résoudre un problème. L'objectif premier est de pouvoir comparer l'efficacité d'algorithmes résolvant le même problème.

Pour un même problème donné, il existe souvent plusieurs algorithmes, et certains sont plus efficaces que d'autres. Cette question est très importante : pour des données volumineuses, la différence entre les durées d'exécution de deux algorithmes résolvant le même problème peut être de l'ordre de plusieurs jours, voire de plusieurs années, voire impossible à résoudre sur des ordinateurs modernes.

Il existe deux types de calculs de complexité : la complexité en temps et la complexité en mémoire (ou en taille). Nous nous intéresserons dans ce cours uniquement à la complexité en temps.

La complexité en temps est directement liée au nombre d'opérations élémentaires qui doivent être exécutées afin de résoudre un problème donné.

Les règles que nous utilisons pour comparer et évaluer les algorithmes ne doivent pas dépendre des qualités d'une machine ou d'un choix de technologie. La raison est que le même programme s'exécutera plus ou moins vite selon la machine, mais que le nombre d'opérations ne changera pas.

On compare la « qualité » des algorithmes pour des données de grande taille (comportement asymptotique). Il n'y a pas d'intérêt à connaître la qualité d'un algorithme pour de très petites quantités de données, puisque dans ce cas, quel que soit l'algorithme choisi, les temps d'exécution seront rapides.

1. Opérations élémentaires et fonction T(n)

Pour calculer la complexité en temps, on examine chaque ligne de code et on lui attribue un « coût ». Le coût ainsi obtenu n'a pas d'unité : il s'agit d'un nombre d'opérations dont chacune aurait le même temps d'exécution (1 unité).

Définition — Opérations élémentaires :

On appelle opération élémentaire :

une opération arithmétique entre deux nombres (+ - * / % //), ou une opération de base sur les listes ;
un accès mémoire : affectation, lecture ou écriture d'une variable ;
une comparaison de valeurs (<, >, ==, …) ;
un appel ou un retour de fonction.

Définition — Complexité temporelle T(n) :

Pour déterminer la complexité en temps d'un algorithme, on compte le nombre d'opérations élémentaires et on exprime ce nombre en fonction des paramètres d'entrée, souvent un entier $n$. La complexité en temps est donc une fonction notée $T$ (pour time) dépendant de la taille $n$ des données. Elle est obtenue en sommant les coûts de toutes les opérations effectuées lors de l'exécution de l'algorithme.

On peut distinguer trois formes de complexité en temps :

la complexité dans le meilleur des cas : c'est la situation la plus favorable ;
la complexité dans le pire des cas : c'est la situation la plus défavorable ;
la complexité en moyenne : la difficulté ici est de définir une entrée « moyenne » pour un problème particulier.

Dans la pratique, on calculera le plus souvent la complexité dans le pire des cas, car elle est la plus pertinente. Il vaut mieux en effet toujours envisager le pire.

2. Exemples de calcul de T(n)

Exemple 1.

L'instruction x = c * 3 nécessite 3 opérations élémentaires : lecture de c, calcul du produit, affectation du résultat à x. On peut noter $T(n) = 3$.

Exemple 2. Recherche du maximum dans une liste de $n$ nombres.

max = tab[0]      # tab = liste de n nombres
for i in range(1, n):
    if tab[i] > max:
        max = tab[i]

On commence par lister les différentes opérations élémentaires utilisées dans ce programme :

accès à un élément d'un tableau ;
lecture de la valeur d'une variable ;
affectation de flottants ;
affectation d'entiers ;
comparaison de deux entiers ;
comparaison de deux flottants.

On peut remarquer que pour $n$ tests de la boucle for effectués, on exécute $n - 1$ fois l'expression à l'intérieur de cette boucle.

On va maintenant compter le nombre de fois où chaque opération élémentaire est effectuée pour chaque ligne, dans le pire des cas (tableau trié par ordre croissant). On place ces calculs dans le tableau suivant :

Ligne	Accès tableau	Accès variable	Affect. entier	Affect. flottant	Comp. flottants
1	1			1
2	n − 1		n − 1
3	n − 1	n − 1			n − 1
4	n − 1		n − 1

Au total, on compte $7n - 5$ opérations élémentaires dans le pire des cas, soit $T(n) = 7n - 5$.

III. Notation de Landau — Grand O

Pour effectuer des comparaisons entre des algorithmes, on raisonne sur de très grands nombres de données, car plus il y a de données, plus les différences entre les algorithmes sont flagrantes.

Pour comparer des algorithmes, il n'est pas nécessaire de connaître précisément la fonction $T$. Nous allons nous intéresser uniquement à ce que l'on appelle l'ordre de grandeur asymptotique à l'aide de la notation de Landau $O$ (« grand O »), dans le pire des cas.

Remarque : La définition précise de l'ordre de grandeur asymptotique n'est pas au programme. Il faut juste savoir que cet ordre de grandeur concerne les cas où l'on prend $n$ très très grand.

Définition — Notation de Landau $O$ :

On dit que $f(n)$ est $O(g(n))$ s'il existe un entier $n_0 > 1$ et une constante positive $c$ tels que, quel que soit $n \geq n_0$ : $$f(n) \leq c \times g(n)$$ Autrement dit, il existe un seuil $n_0$ à partir duquel la fonction $f$ est toujours inférieure à $g$, à une constante multiplicative fixée $c$ près. Cette notation indique que, dans le pire des cas, à partir d'un certain seuil, la croissance de $f$ ne dépassera pas celle de $g$.

1. Exemples

$T(n) = 2n + 10$ est $O(n)$ : on peut facilement prouver que pour tout $n \geq 10$, $2n + 10 \leq 3n$. Donc en choisissant $n_0 = 10$ et $c = 3$, on a bien, pour tout entier $n \geq n_0$, $f(n) \leq c \times n$.

Par contre, $k(n) = n^2$ n'est pas $O(n)$, car $n^2 \geq cn \Leftrightarrow n \geq c$ ne peut être satisfaite pour tout $n$ puisque $c$ est une constante.

2. Règles pratiques de la notation $O$

Si $T(n)$ est un polynôme de degré $d$, alors $T(n)$ est $O(n^d)$.
- On peut supprimer les termes de degré inférieur à $d$.
- On peut supprimer les facteurs constants.
En pratique, on utilise la classe la plus basse possible : on dit que « $2n$ est $O(n)$ » même si techniquement « $2n$ est $O(n^2)$ » est aussi vrai.
On utilise l'expression la plus simple : on dit que « $3n + 5$ est $O(n)$ » plutôt que « $3n + 5$ est $O(3n)$ ».

Remarque : Comme les facteurs constants et les termes de degré inférieur sont supprimés lors du passage à la notation $O$, on peut les « oublier » lors du décompte des opérations élémentaires. Par exemple, on a vu que le programme de recherche du maximum exécute au plus $7n - 5$ opérations élémentaires : on peut donc dire que cet algorithme a une complexité en $O(n)$ (complexité linéaire).

IV. Classes de complexité

Les complexités algorithmiques vont être exprimées comme des $O$ de fonctions mathématiques considérées comme des fonctions de référence. Cela permet de les classer en comparant la croissance de ces fonctions.

Des algorithmes appartenant à une même classe seront considérés comme de complexité équivalente et donc d'efficacité comparable.

Les fonctions de référence les plus courantes sont : $f_1(n)=1$, $f_2(n)=\log(n)$, $f_3(n)=n$, $f_4(n)=n \times \log(n)$, $f_5(n)=n^2$, $f_6(n)=n^3$, $f_7(n)=2^n$ et $f_8(n)=n!$.

Pour visualiser le comportement de ces fonctions, elles sont tracées ci-dessous :

Le tableau suivant récapitule les classes de complexité de référence :

Ces complexités sont rangées dans l'ordre croissant de croissance des fonctions associées.

V. Ordres de grandeur des temps d'exécution

Pour donner un ordre d'idée sur les différentes complexités, le tableau ci-dessous présente les classes de complexité, leur nom, des temps d'exécution estimés et un exemple de problème. Les temps d'exécution sont estimés sur la base d'un accès mémoire de 10 nanosecondes par étape. Ces valeurs n'ont aucune valeur réaliste absolue (lors d'une exécution sur machine, de nombreux mécanismes entrent en jeu) mais fournissent un ordre de grandeur utile pour comparer les algorithmes entre eux.

Tableau des temps d'exécution selon les complexités

VI. Limites du modèle

Le modèle de complexité présenté dans ce cours est une approximation de la réalité. Par exemple, il ne tient pas compte du fait que certaines opérations dites élémentaires sont beaucoup plus coûteuses que d'autres : calculer le produit de deux très grands entiers est bien plus coûteux en temps que calculer leur somme.

De plus, même un algorithme ayant une complexité théoriquement « mauvaise » peut se révéler intéressant dans le cas où on l'utilise sur une petite quantité de données, surtout si le pire des cas n'arrivera jamais dans le cadre du programme que l'on est en train de coder.