Annexe A  Le coût d’un algorithme

• Une définition très informelle des algorithmes
• Des algorithmes “efficaces” ?
• Quelques exemples
• Coût estimé vs. coût réel

Ce chapitre rappelle les différents moyens d’évaluer le coût d’un algorithme.

A.1  Une définition très informelle des algorithmes

La formalisation de la notion d’algorithme est assez tardive. Les travaux fondamentaux de Post et de Turing datent de la fin des années 30. Nous ne disposons pas, pour ce cours, des outils qui permettent d’exposer très rigoureusement la notion d’algorithme et de complexité algorithmique. Nous nous contenterons de la définition suivante : Un algorithme est un assemblage ordonné d’instruction élémentaires qui à partir d’un état initial bien spécifié permettent d’aboutir à un état final, lui aussi bien spécifié. Notons que pour qu’un algorithme puisse s’exécuter, les données (d’entrées, de sortie et intermédiaires) sont structurées. Ceci permet de les conserver, de les utiliser et de les modifier.

Les étapes élémentaires sont éventuellement répétées (notion de boucle) et sont soumises à des test logiques (instruction de contrôle). Les algorithmes peuvent, la plupart du temps, être codés à l’aide de programmes informatique

A.2  Des algorithmes “efficaces” ?

Qu’est-ce qu’un bon algorithme ? C’est bien entendu un algorithme qui répond correctement au problème posé. On souhaite généralement qu’il soit aussi rapide et n’utilise pas trop de mémoire.

Quel que soit la mesure choisie, il est clair que la qualité de l’algorithme n’est pas absolue mais dépend des données d’entrée. Les mesures d’efficacité sont donc des fonctions des données d’entrée. Pour évaluer le temps d’exécution d’un algorithme (par exemple un tri) sur une donnée d (par exemple un ensemble d’entiers à trier), on calcule le nombre d’opérations élémentaires (opérations arithmétiques, affectation, instruction de contrôle, etc.) effectuées pour traiter la donnée d. On admet communément que toute opération élémentaire prend un temps constant. Attention, cette hypothèse n’est valable que si tous les nombres sont codés sur un même nombre de bits.

Plutôt que de calculer le nombre d’opérations associé à chaque donnée, on cherche souvent à évaluer le nombre d’opérations nécessaires pour traiter les données qui ont une certaine “taille”. Il existe souvent un paramètre naturel qui est un estimateur raisonnable de la taille d’une donnée (par exemple, le nombre n d’éléments à trier pour un algorithme de tri, la taille n,m d’une matrice pour le calcul du déterminant, la longueur n d’une liste pour une inversion, etc.). Pour simplifier nous supposerons dans la suite que la “taille” d’une donnée est évaluée par un unique entier n.

Les informaticiens s’intéressent à l’ordre de grandeur des temps d’exécution (ou de taille mémoire) quand n devient très grand. Le coût exact en secondes est en effet très difficile à mesurer et dépend de très nombreux paramètres (cf. Section A.4). On utilise donc les notations O, Θ et Ω pour exprimer des relations de domination : Soient f et g deux fonctions définies des entiers naturels vers les entiers naturels.

• f(n) = O(g(n)) si et seulement si il existe deux constantes positives n₀ et B telles que

  ∀  n ≥ n0, f(n) ≤ B g(n)

  Ce qui signifie que f ne croît pas plus vite que g. Un algorithme en O(1), c’est un algorithme dont le temps d’exécution ne dépend pas de la taille des données. C’est donc un ensemble constant d’opérations élémentaires (exemple : l’addition de deux entiers). On dit d’un algorithme qu’il est linéaire si il utilise O(n) opérations élémentaires. Il est polynomial si il existe une constante a telle que le nombre total d’opérations élémentaires est O(n^a).
• f(n) = Ω(g(n)) si et seulement si il existe deux constantes positives n₀ et B telles que

  ∀  n ≥ n0, f(n) ≥ B g(n)

• f(n) = Θ(g(n)) si et seulement si il existe trois constantes positives n₀,B et C telles que

  ∀  n ≥ n0, B  g(n) ≤ f(n) ≤ C g(n)

Dans la pratique, le temps d’exécution d’un algorithme dépend non seulement de n mais aussi de la structure des données. Par exemple, le tri d’une liste d’entiers est, pour certains algorithmes, plus rapide si la liste est partiellement triée plutôt que dans un ordre parfaitement aléatoire. Pour analyser finement un algorithme, on a donc besoin de plusieurs mesures :

• La complexité dans le “pire cas”. On mesure alors le nombre d’opérations avec les données qui mènent à un nombre maximal d’opérations. Soit donc

  complexité dans le pire cas =

  max d  donnée de taille  n

  C(d)

  où C(d) est le nombre d’opérations élémentaires pour exécuter l’algorithme sur la donnée d’entrée d.
• La complexité en moyenne. Cette notion n’a de sens que si l’on dispose d’une hypothèse sur la distribution des données. Soit donc

  complexité en moyenne =

  ∑ d  donnée de taille  n

  π(d) C(d)

  où π(d) est la probabilité d’avoir en entrée une instance d parmi toutes les données de taille n.

Ces notions s’étendent à la consommation mémoire d’un algorithme. On parle alors de complexité spatiale (maximale ou moyenne).

En pratique, le pire cas est rarement atteint et l’analyse en moyenne semble plus séduisante. Attention tout de même à deux écueils pour les calculs en moyenne :

• Pour que ce calcul garde un certain sens, il faut connaître la distribution des données, ce qui est délicat à estimer. On fait parfois l’hypothèse que les données sont équiprobables (ce qui est bien souvent totalement arbitraire).
• Comme nous allons le voir, les calculs de complexité en moyenne sont fort délicats à mettre en œuvre.

A.3  Quelques exemples

Nous donnons ici des exemples simples et variés d’analyse d’algorithmes. De nombreux autres exemples sont dans le polycopié.

A.3.1  Factorielle

La première version de notre programme permettant de calculer n! est itérative.

Nous avons n−1 itérations au sein desquelles le nombre d’opérations élémentaires est constant. La complexité est O(n)

La seconde version est récursive. Soit C(n) le nombre d’opérations nécessaires pour calculer factorielle(n). Nous avons alors C(n) ≤ λ + C(n−1) où λ est une constante qui majore le nombre d’opérations précédent l’appel récursif. De plus C(1) se calcule en temps constant et donc C(n) = O(n).

A.3.2  Recherche Dichotomique

Considérons un tableau T de n entiers triés. On cherche à tester si un entier v donné se trouve dans le tableau. Pour ce faire, on utilise une recherche “dichotomique”.

La fonction trouve cherche l’entier v dans T entre les indices min et max -1. Pour effectuer une recherche sur tout le tableau, il suffit d’appeler trouve(T, v, 0, T.length).

Le nombre total d’opérations est proportionnel au nombre de comparaisons C(n) effectuées par l’algorithme récursif. Et donc, nous avons immédiatement : C(n) = 1 + C(n/2). Soit donc, C(n) = O(logn).

A.3.3  Tours de Hanoi

Le très classique problème des “tours de Hanoi” consiste à déplacer des disques de diamètres différents d’une tour de départ à une tour d’arrivée en passant par une tour intermédiaire. Les règles suivantes doivent être respectées : on ne peut déplacer qu’une disque à la fois, et on ne peut placer un disque que sur un disque plus grand ou sur un emplacement vide.

Identifions les tours par un entier. Pour résoudre ce problème, il suffit de remarquer que si l’on sait déplacer une tour de taille n de la tour ini vers dest, alors pour déplacer une tour de taille n+1 de ini vers dest, il suffit de déplacer une tour de taille n de ini vers temp, un disque de ini versdest et finalement la tour de hauteur n detemp versdest.

Notons C(n) le nombre d’instructions élémentaires pour calculer hanoi(n, ini, temp, dest). Nous avons alors C(n+1) ≤ 2 C(n) + λ, où λ est une constante. Tour de Hanoi est exponentielle.

A.3.4  Recherche d’un nombre dans un tableau, complexité en moyenne

On suppose que les éléments d’un tableau T de taille n sont des nombres entiers distribués de façon équiprobable entre 1 et k (une constante). Considérons maintenant l’algorithme de recherche ci-dessous qui cherche une valeur v dans T.

La complexité dans le pire cas est clairement O(n). Quelle est la complexité en moyenne ?

Remarquons que nous avons kⁿ tableaux. Parmi ceux-ci, (k−1)ⁿ ne contiennent pas v et dans ce cas, l’algorithme procède à exactement n itérations. Dans le cas contraire, l’entier est dans le tableau et sa première occurrence est alors i avec une probabilité de

et il faut alors procéder à i itérations. Au total, nous avons une complexité moyenne de

Or

(il suffit pour établir ce résultat de dériver l’identité ∑_{i = 1}ⁿ xⁱ = 1 − xⁿ⁺¹/1−x) et donc

A.4  Coût estimé vs. coût réel

Les mesures présentées dans ce chapitre ne sont que des estimations asymptotique des algorithmes. En pratique, il faut parfois atteindre de très grandes valeurs de n pour qu’un algorithme en O(n logn) se comporte mieux qu’un algorithme quadratique.

Les analyses de complexité peuvent servir à comparer des algorithmes mais le modèle de coût est relativement simple (par exemple, les opérations d’accès aux disques, ou le trafic réseau généré ne sont pas pris en compte alors que ces paramètres peuvent avoir une influence considérable sur un programme). Il est toujours nécessaire de procéder à des analyses expérimentales avant de choisir le “meilleur” algorithme, i.e., l’algorithme spécifiquement adapté au problème que l’on cherche à résoudre.