Langage de programmation - Mathématiques appliquées

Analyse asymptotique

L'analyse asymptotique est une branche des mathématiques appliquées et de l'informatique théorique qui étudie le comportement d'une fonction lorsque sa variable tend vers une valeur limite, généralement l'infini. En algorithmique, elle est principalement utilisée pour mesurer la croissance du temps d'exécution ou de la consommation mémoire d'un algorithme lorsque la taille des données augmente.

Contrairement à une mesure expérimentale réalisée sur un ordinateur particulier, l'analyse asymptotique fournit une estimation indépendante du processeur, du système d'exploitation, du compilateur ou du langage de programmation utilisé. Elle permet ainsi de comparer objectivement plusieurs algorithmes réalisant une même tâche.

Les notations asymptotiques, telles que O, Ω, Θ, o et ω, constituent aujourd'hui un langage universel pour exprimer les performances des algorithmes. Elles interviennent dans l'étude des structures de données, des graphes, de la programmation dynamique, de la théorie de la complexité, des compilateurs, de l'intelligence artificielle, des bases de données et de nombreuses autres disciplines de l'informatique.

Définition

L'analyse asymptotique consiste à étudier la vitesse de croissance d'une fonction lorsque :

n → ∞

où :

représente généralement la taille des données à traiter.

Plutôt que de calculer précisément le temps d'exécution, on cherche à déterminer son ordre de grandeur.

Pourquoi utiliser l'analyse asymptotique ?

Le temps d'exécution réel dépend de nombreux facteurs :

la vitesse du processeur ;
la quantité de mémoire disponible ;
le compilateur ;
les optimisations du compilateur ;
le système d'exploitation ;
le langage de programmation.

L'analyse asymptotique élimine ces facteurs afin de ne conserver que la croissance fondamentale de l'algorithme.

Taille du problème

La variable :

désigne généralement :

le nombre d'éléments d'un tableau ;
le nombre de sommets d'un graphe ;
le nombre de caractères d'une chaîne ;
le nombre de lignes d'une base de données ;
le nombre de noeuds d'un arbre.

Toutes les estimations sont exprimées en fonction de cette taille.

Idée fondamentale

Lorsque :

devient très grand, certains termes deviennent négligeables.

Par exemple :

3n²
+
25n
+
100

est dominé par :

3n²

Lorsque :

tend vers l'infini, les termes :

25n

et :

100

deviennent insignifiants devant :

n²

Simplification

Ainsi :

3n²
+
25n
+
100

est simplement écrit :

O(n²)

Les constantes multiplicatives sont également ignorées.

Par exemple :

1000n

appartiennent tous deux à :

O(n)

Notation grand O

La notation :

O(f(n))

décrit une borne supérieure asymptotique.

Elle signifie que la fonction étudiée ne croît pas plus rapidement que :

f(n)

à une constante multiplicative près.

Définition formelle du grand O

Une fonction :

g(n)

est dans :

O(f(n))

s'il existe deux constantes positives :

n₀

telles que :

g(n)
≤
cf(n)

pour tout :

n ≥ n₀

Exemple

Considérons :

g(n)=5n+20

Pour :

n ≥ 20

on a :

5n+20
≤
6n

Donc :

5n+20
∈
O(n)

Signification pratique

Dire qu'un algorithme possède une complexité :

O(n²)

ne signifie pas qu'il effectue exactement :

n²

opérations.

Cela signifie seulement que son temps d'exécution croît au plus comme une constante multipliée par :

n²

pour des valeurs suffisamment grandes de :

Notation grand Ω

La notation :

Ω(f(n))

représente une borne inférieure.

Elle indique que la fonction croît au moins aussi rapidement que :

f(n)

Définition formelle de Ω

Une fonction :

g(n)

appartient à :

Ω(f(n))

s'il existe :

c > 0

n₀

tels que :

g(n)
≥
cf(n)

pour :

n ≥ n₀

Exemple

La fonction :

4n²+10

appartient à :

Ω(n²)

car elle reste toujours supérieure à une constante multipliée par :

n²

pour les grandes valeurs de :

Notation grand Θ

La notation :

Θ(f(n))

indique une borne supérieure et une borne inférieure simultanément.

Autrement dit :

Θ(f(n))
=
O(f(n))
∩
Ω(f(n))

Exemple

La fonction :

7n²
+
10n
+
5

est :

Θ(n²)

car elle est à la fois :

O(n²)

Ω(n²)

Petit o

La notation :

o(f(n))

exprime une croissance strictement plus lente.

Elle signifie :

lim g(n)/f(n)=0

Exemple

On obtient :

n
∈
o(n²)

car :

lim n/n²
=
0

Petit ω

La notation :

ω(f(n))

exprime une croissance strictement plus rapide.

Elle vérifie :

lim g(n)/f(n)
=
∞

Exemple

On obtient :

n²
∈
ω(n)

car :

lim n²/n
=
∞

Comparaison des notations

Notation	Signification
O	Borne supérieure
Ω	Borne inférieure
Θ	Borne exacte
o	Strictement inférieur
ω	Strictement supérieur

Hiérarchie des croissances

Les principales fonctions apparaissent généralement dans l'ordre suivant :

log n

√n

n log n

n²

n³

2ⁿ

Chaque niveau devient beaucoup plus coûteux lorsque :

augmente.

Croissance constante

Une complexité constante :

O(1)

ne dépend pas de la taille des données.

Exemple :

MODULE Premier(Tableau)

RETOURNER
Tableau[0]

Le nombre d'opérations reste identique.

Croissance logarithmique

Une complexité :

O(log n)

réduit progressivement la taille du problème.

Exemple classique :

recherche binaire ;
arbres AVL ;
arbres rouges-noirs.

Exemple de recherche dichotomique

À chaque étape :

devient :

n/2

Après :

étapes :

n/2^k
=
1

On obtient :

k
=
log₂n

Complexité linéaire

Une complexité :

O(n)

parcourt généralement tous les éléments.

Exemple :

MODULE Maximum(Tableau)
   maximum ← Tableau[0]
   POUR i ← 1 JUSQU'A n
      SI Tableau[i]>maximum ALORS
         maximum ← Tableau[i]
      FIN SI
   FIN POUR
   RETOURNER maximum

Complexité linéaire logarithmique

Une complexité :

O(n log n)

est typique des meilleurs algorithmes de tri par comparaison.

Exemples :

tri fusion ;
tri par tas ;
tri rapide (cas moyen).

Pourquoi n log n ?

Dans le tri fusion : l'arbre possède :

log₂n

niveaux.

Chaque niveau traite :

éléments.

Le coût total est :

n log n

Complexité quadratique

Une complexité :

O(n²)

apparaît souvent avec deux boucles imbriquées.

POUR i
   POUR j

      ...

   FIN POUR
FIN POUR

Complexité cubique

Trois boucles imbriquées produisent généralement :

O(n³)

Exemple : multiplication matricielle classique.

Complexité exponentielle

Une complexité :

O(2ⁿ)

augmente extrêmement rapidement.

Elle apparaît dans :

retour arrière ;
sous-ensembles ;
SAT naïf.

Complexité factorielle

La complexité :

O(n!)

correspond à l'exploration de toutes les permutations.

Exemple :

problème du voyageur de commerce naïf.

Comparaison numérique

n	n	n²	n³	2ⁿ	n!
5	5	25	125	32	120
10	10	100	1000	1024	3 628 800
20	20	400	8000	1 048 576	2,43×10¹⁸

Limites

Les fonctions :

2ⁿ

et :

deviennent rapidement impossibles à calculer.

Analyse d'une boucle

Une boucle :

POUR i ← 1 JUSQU'A n

effectue :

itérations.

La complexité est donc :

O(n)

Deux boucles indépendantes

POUR i
FIN POUR

POUR j
FIN POUR

Le coût est :

n+n
=
2n

soit :

O(n)

Deux boucles imbriquées

POUR i

POUR j

FIN POUR

FIN POUR

Le coût est :

n²

Boucle logarithmique

TANT QUE n>1
n ← n/2
FIN TANT QUE

Le nombre d'itérations est :

O(log n)

Boucles mixtes

POUR i
   j ← n
   TANT QUE j>1
      j ← j/2
   FIN TANT QUE
FIN POUR

Le coût est :

O(n log n)

Analyse récursive

Une fonction récursive conduit souvent à une relation de récurrence.

Par exemple :

T(n)
=
T(n-1)
+
1

Sa solution est :

O(n)

Recherche binaire

T(n)
=
T(n/2)
+
1

Solution :

O(log n)

Tri fusion

T(n)
=
2T(n/2)
+
n

Solution :

O(n log n)

Karatsuba

T(n)
=
3T(n/2)
+
n

Solution :

O(n^log₂3)

Théorème maître

Le théorème maître résout :

T(n)
=
aT(n/b)
+
f(n)

Il permet d'obtenir directement l'ordre asymptotique.

Cas moyen

Un algorithme peut posséder plusieurs complexités.

Par exemple :

Cas	Complexité
Meilleur	O(n)
Moyen	O(n log n)
Pire	O(n²)

Meilleur cas

Le meilleur cas représente la situation la plus favorable.

Exemple : recherche linéaire lorsque l'élément est trouvé immédiatement.

Pire cas

Le pire cas garantit une borne maximale.

C'est généralement celui utilisé en algorithmique.

Cas moyen

Le cas moyen repose sur des hypothèses probabilistes.

Il est souvent plus représentatif de l'utilisation réelle.

Analyse mémoire

L'analyse asymptotique s'applique également à la mémoire.

Exemple :

Tableau[n]

utilise :

O(n)

mémoire.

Mémoire constante

Quelques variables seulement :

entier

réel

booléen

produisent :

O(1)

Pile récursive

Une récursion de profondeur :

consomme :

O(n)

mémoire.

Approximation

L'analyse asymptotique ignore :

les constantes ;
les petites valeurs de :

les optimisations locales.

Elle décrit uniquement la tendance générale.

Erreur fréquente

Dire :

100n²

est plus lent que :

n³

n'est vrai que pour certaines petites valeurs.

Lorsque :

devient suffisamment grand :

n³

croît toujours plus rapidement.

Limites de l'analyse

Deux algorithmes de même complexité :

O(n)

peuvent avoir des performances très différentes.

Les constantes cachées peuvent être importantes.

Analyse expérimentale

En pratique, on combine souvent :

analyse asymptotique ;
mesures expérimentales ;
profils d'exécution.

Optimisation

L'analyse asymptotique permet d'identifier les parties critiques d'un programme.

Réduire :

O(n²)

à :

O(n log n)

peut représenter un gain considérable.

Applications

L'analyse asymptotique est utilisée dans :

l'analyse des algorithmes ;
les compilateurs ;
les graphes ;
les arbres ;
la cryptographie ;
les bases de données ;
les moteurs de recherche ;
l'intelligence artificielle ;
la programmation dynamique ;
les réseaux ;
le traitement d'images ;
le calcul scientifique.

Algorithme d'estimation

MODULE Complexité(Boucles)

   Identifier
      les boucles

   Identifier
      les appels récursifs

   Déterminer
      la relation de récurrence

   Simplifier
      les termes dominants

   RETOURNER
      l'ordre asymptotique

Exemple Java


public static int maximum(int[] tableau) {
 
    int maximum = tableau[0];
 
    for (int i = 1; i < tableau.length; i++) {
 
        if (tableau[i] > maximum)
            maximum = tableau[i];
 
    }
 
    return maximum;
 
}

Ce programme parcourt une seule fois le tableau.

Sa complexité temporelle est :

O(n)

Sa complexité mémoire est :

O(1)

Tableau récapitulatif

Complexité	Exemple
O(1)	Accès à un tableau
O(log n)	Recherche binaire
O(n)	Recherche linéaire
O(n log n)	Tri fusion
O(n²)	Tri à bulles
O(n³)	Multiplication matricielle classique
O(2ⁿ)	Génération des sous-ensembles
O(n!)	Génération des permutations

Avantages

L'analyse asymptotique présente de nombreux avantages :

elle permet de comparer objectivement des algorithmes indépendamment du matériel utilisé ;
elle met en évidence la vitesse de croissance des temps d'exécution et de la mémoire ;
elle simplifie l'étude des algorithmes complexes en ne conservant que les termes dominants ;
elle constitue la base de la théorie de la complexité algorithmique ;
elle guide le choix des structures de données et des techniques de programmation ;
elle facilite l'analyse des algorithmes récursifs grâce aux relations de récurrence ;
elle permet d'anticiper les limites de passage à l'échelle d'une application ;
elle est universellement utilisée dans la littérature scientifique et technique.

Limites et précautions

L'analyse asymptotique possède néanmoins certaines limites :

elle ne fournit pas le temps d'exécution exact d'un programme ;
elle ignore les constantes multiplicatives et les termes de faible ordre ;
elle décrit le comportement pour de grandes valeurs de n, mais peut être moins représentative pour de petits jeux de données ;
deux algorithmes ayant la même complexité asymptotique peuvent présenter des performances très différentes en pratique ;
elle ne tient pas compte des effets de cache, de la parallélisation ou des optimisations spécifiques du compilateur ;
certains algorithmes possèdent un excellent cas moyen mais un mauvais pire cas ;
l'analyse mémoire est parfois aussi importante que l'analyse temporelle ;
elle doit être complétée par des mesures expérimentales pour évaluer les performances réelles.

Remarque

L'analyse asymptotique constitue l'un des fondements de l'algorithmique moderne. Grâce aux notations O, Ω, Θ, o et ω, elle permet de décrire rigoureusement la croissance des fonctions et d'évaluer l'efficacité des algorithmes indépendamment de leur implémentation. Associée aux relations de récurrence, aux fonctions génératrices et aux techniques de programmation dynamique, elle offre un cadre mathématique puissant pour concevoir, comparer et optimiser les algorithmes utilisés dans tous les domaines de l'informatique.

Dernière mise à jour : Jeudi, le 16 juillet 2026