Conception et analyse d’algorithmes

Ce document présente les notions fondamentales de la conception et de l’analyse d’algorithmes, destinées aux étudiants de deuxième année en informatique. Il couvre la complexité des algorithmes et des problèmes, les paradigmes de programmation, ainsi que les arbres équilibrés. L’objectif est de fournir des bases solides pour comprendre comment évaluer et comparer l’efficacité des algorithmes.

Complexité des algorithmes

Qu’est-ce qu’un algorithme ?

Un algorithme est un ensemble d’actions visant à résoudre un problème donné. Il agit sur des données initiales (entrées), produit des résultats (sorties) ou des effets, doit se terminer pour toutes les données possibles et fournir une solution correcte dans chaque cas.

La programmation d’un algorithme consiste à l’exprimer dans un langage de programmation et à l’exécuter sur une machine donnée (processeur, mémoire). Un même algorithme peut avoir plusieurs variantes de programmes, selon le style de programmation (itératif, récursif, etc.).

Motivation du calcul de complexité

Pour un problème donné, plusieurs algorithmes peuvent exister. Il est donc important de savoir s’il y a un intérêt à choisir l’un plutôt que l’autre, et comment faire ce choix. Par exemple, le nombre d’ordres possibles d’une liste de n éléments est n!. Appliquer une opération simple à toutes ces listes devient vite impossible dès que n augmente (17! ≈ 3,5 × 10¹⁴).

Définition de la complexité d’un algorithme

La complexité étudie l’efficacité comparée des algorithmes en mesurant :

• la complexité spatiale : la taille approximative des données en mémoire,
• la complexité temporelle : le temps d’exécution de l’algorithme.

Exemple : la représentation d’une matrice creuse peut se faire par un tableau 2D ou une liste chaînée contenant uniquement les éléments non nuls, avec leurs indices de ligne et colonne.

Une bonne maîtrise de la complexité permet de concevoir des applications qui tournent en un temps prévisible et utilisent un espace mémoire contrôlé.

Calcul de la complexité : taille des données

La complexité dépend notamment de la taille des données à traiter. Un algorithme sur une dizaine d’éléments ne prendra pas autant de temps que le même sur un millier d’éléments. Il faut donc évaluer la taille pertinente des données, qui peut être :

• le nombre lui-même,
• la longueur d’un mot,
• le nombre d’éléments dans une liste ou un tableau,
• pour une matrice m × n : max(m, n), m × n ou m + n.

Le choix de la structure de données influence aussi l’efficacité de l’algorithme.

Calcul de la complexité : type des opérations

Les opérations effectuées par un algorithme n’ont pas toutes la même durée :

• une addition est plus rapide qu’une élévation à la puissance,
• une comparaison est plus rapide qu’un accès à une donnée dans un fichier.

Pour simplifier, on suppose souvent que toutes les opérations ont un coût uniforme et constant, même si ce n’est pas toujours réaliste.

Complexité au pire, au mieux et en moyenne

Soit A un algorithme appliqué sur des données d ∈ D, et T(A, d) le temps d’exécution en fonction de d. On distingue :

• le pire cas : TMax(A, D) = max{T(A, d), d ∈ D},
• le meilleur cas : TMin(A, D) = min{T(A, d), d ∈ D},
• la moyenne : TMoy(A, D) = Σ p(d) × T(A, d), où p(d) est la probabilité d’avoir la donnée d.

Exemple : recherche d’un élément dans un tableau.

On a la propriété suivante :

TMin(A, D) ≤ TMoy(A, D) ≤ TMax(A, D)

On s’intéresse généralement à la complexité dans le pire cas.

Calcul de complexité des algorithmes itératifs

Dans un programme strictement itératif (sans récursivité), les boucles sont disjointes ou imbriquées.

Notation : T(n) est le nombre d’opérations élémentaires.

• Pour une séquence de traitements :

T(n) = T1(n) + T2(n)

• Pour un embranchement conditionnel :

si <condition> alors
  Traitement1 T1(n)
sinon
  Traitement2 T2(n)

T(n) = Tc(n) + max(T1(n), T2(n))

• Pour une boucle :

tant que <condition> faire
  Traitement Ti(n)
fin tant que

T(n) = (k + 1) × Tc(n) + Σ (i=1 à k) Ti(n)

Calcul de complexité des algorithmes récursifs

Pour une fonction récursive, la complexité s’exprime souvent par une équation récursive.

Exemple :

si (n > 1) alors
  FunctionRecursive(n)
    FunctionRecursive(n / 2)
    Traitement(n)
    FunctionRecursive(n / 2)

coût T(n / 2)
coût C(n)
coût T(n / 2)

Équation récursive : T(n) = 2 × T(n / 2) + C(n)

Exemple : extrait du tri par sélection

min ← i  // 1 affectation
pour j de i + 1 à n faire  // 1 affectation + 1 comparaison + (1 affectation + 1 comparaison) boucle
  si A[j] < A[min] alors  // 1 comparaison boucle
    min ← j  // si test vrai : 1 affectation boucle

Dans le pire cas (tableau trié en ordre inverse), le coût est :

4 × (n − i) + 3

Dans le meilleur cas (tableau déjà trié), on n’exécute jamais l’instruction min ← j, et le coût est :

3 × (n − i + 1)

En moyenne, si la moitié des tests est vraie :

4 × (n − i) / 2 + 3 × (n − i) / 2 + 3

Estimation asymptotique

En complexité, on ne cherche pas à évaluer précisément les temps d’exécution (qui dépendent de la machine), mais à obtenir des approximations.

On dit que T est asymptotiquement majorée par f lorsque n → ∞, et on utilise la notation de Landau :

T(n) = O(f(n)) si ∃ c, n0 tels que ∀ n > n0, T(n) ≤ c × f(n)

On dit que T est du même ordre de grandeur que f et on note :

T(n) = Θ(f(n)) si ∃ c1, c2, n0 tels que ∀ n > n0, c1 × f(n) ≤ T(n) ≤ c2 × f(n)

Exemples d’estimations asymptotiques

• f(n) = n³ + 2n² + 4n + 2 = O(n³) (car pour n ≥ 1, f(n) ≤ 8 × n³)
• f(n) = n log(n) + 12n + 888 = O(n log(n))
• f(n) = 1000 n¹⁰ − n⁷ + 2n = O(2ⁿ)

Principales classes de complexité

• O(1) : temps constant, indépendant de la taille des données.
• O(log n) : temps logarithmique, typique des algorithmes qui divisent le problème en sous-problèmes plus petits. Exemple : recherche dichotomique dans une liste triée.
• O(n) : temps linéaire, obtenu lorsqu’un traitement constant est effectué sur chaque donnée. Exemple : recherche d’un élément dans une liste.
• O(n log n) : algorithmes qui divisent le problème en plusieurs sous-problèmes indépendants, puis combinent les résultats. Exemple : tri fusion.
• O(n²) : temps quadratique, souvent dû à des boucles imbriquées parcourant toutes les paires de données.
• O(n³) : temps cubique, extension du temps quadratique.
• O(2ⁿ) : temps exponentiel, souvent lié à une recherche exhaustive de solutions.

Remarque : un algorithme à complexité exponentielle est en pratique inutilisable, tandis que les algorithmes polynomiaux restent efficaces pour des tailles de données raisonnables.

Exemple : tri par dénombrement

Si les valeurs à trier sont comprises entre 0 et max (avec max pas trop grand), on peut trier en comptant le nombre d’occurrences de chaque valeur dans un tableau annexe count où count[i] indique le nombre de i dans le tableau initial. Ensuite, on reconstitue le tableau trié en parcourant count.

1. Écrire cet algorithme.
2. Calculer sa complexité.
3. Discuter cette complexité par rapport à la borne théorique inférieure.

Paradigme Diviser pour Régner

Cette stratégie consiste à scinder un problème en sous-problèmes de même nature sur des instances plus petites, à résoudre ces sous-problèmes, puis à combiner les résultats pour obtenir la solution du problème initial.

Cette démarche est essentiellement récursive et comporte trois étapes à chaque niveau de récursivité :

• Diviser : découper le problème en sous-problèmes ;
• Régner : résoudre récursivement les sous-problèmes ou directement s’ils sont assez petits ;
• Combiner : fusionner les solutions des sous-problèmes en une solution complète.

Exemple : algorithme tri-fusion

Le tri-fusion repose sur la décomposition suivante :

• Diviser : on scinde la séquence de longueur l en deux sous-séquences de taille l/2 ;
• Régner : on trie récursivement chacune des deux sous-séquences si elles contiennent plus d’un élément ;
• Combiner : on fusionne les deux sous-séquences triées en une séquence triée.

La complexité du tri-fusion satisfait l’équation récursive :

T(n) = 2 × T(n/2) + n avec T(1) = 0

Résolution des équations récursives

Pour les équations du type :

T(n) = a × T(n/b) + f(n) avec T(1) = c

on peut utiliser plusieurs méthodes :

• méthode par substitution,
• méthode par développement itératif,
• méthode générale (théorème maître).

Méthode par substitution

Principe : on émet une hypothèse sur la forme de la solution, par exemple :

T(n) = g(n)

puis on vérifie que g(n) satisfait l’équation :

g(n) = a × g(n/b) + f(n) avec g(1) = c

en ajustant les constantes.

Glossaire des termes clés

• Algorithme : ensemble d’actions pour résoudre un problème donné.
• Complexité temporelle : mesure du temps d’exécution d’un algorithme.
• Complexité spatiale : mesure de la mémoire utilisée par un algorithme.
• Complexité au pire cas : temps maximal d’exécution sur toutes les données possibles.
• Complexité au meilleur cas : temps minimal d’exécution.
• Complexité moyenne : moyenne pondérée des temps d’exécution selon la distribution des données.
• Notation O (grand O) : borne supérieure asymptotique d’une fonction.
• Notation Θ (thêta) : ordre de grandeur asymptotique exact.
• Diviser pour Régner : paradigme de résolution par division du problème en sous-problèmes plus petits.
• Tri-fusion : algorithme de tri basé sur le paradigme Diviser pour Régner.

Points clés à retenir

• Un algorithme doit toujours terminer et fournir une solution correcte.
• La complexité mesure l’efficacité d’un algorithme en temps et en espace.
• La taille des données et le type d’opérations influencent la complexité.
• On distingue la complexité au pire, au meilleur et en moyenne.
• La notation asymptotique (O, Θ) permet de comparer les ordres de grandeur des complexités.
• Les principales classes de complexité vont du temps constant O(1) au temps exponentiel O(2ⁿ).
• Le paradigme Diviser pour Régner est une méthode puissante pour concevoir des algorithmes efficaces.
• Le tri-fusion est un exemple classique d’algorithme Diviser pour Régner avec complexité O(n log n).
• Les algorithmes exponentiels sont généralement inutilisables en pratique.