Complexité des algorithmes

#title: "Complexité des algorithmes" description: "Notations asymptotiques, analyse amortie et modèle de calcul"Copier le lien

#Complexité des algorithmesCopier le lien

L'analyse de complexité permet de comparer les algorithmes indépendamment de l'implémentation matérielle. Elle répond à la question fondamentale : comment évolue le temps d'exécution (ou l'espace mémoire) lorsque la taille de l'entrée augmente ?

#Notations asymptotiquesCopier le lien

#Notation O (Grand O)Copier le lien

La notation donne une borne supérieure asymptotique :

Intuition : ne croît pas plus vite que à un facteur constant près.

Exemples :

#Notation Ω (Grand Omega)Copier le lien

La notation donne une borne inférieure :

#Notation Θ (Grand Theta)Copier le lien

La notation donne un encadrement exact :

#Hiérarchie des complexitésCopier le lien

#Modèle RAMCopier le lien

Le modèle RAM (Random Access Machine) est le cadre standard pour l'analyse :

• Chaque instruction élémentaire (addition, comparaison, accès mémoire) coûte
• La mémoire est illimitée et à accès uniforme
• Les opérations arithmétiques sont bornées par la taille des données

Ce modèle simplifié capture l'essentiel du comportement tout en restant indépendant de l'architecture.

#Analyse de complexitéCopier le lien

#Pire cas, meilleur cas, cas moyenCopier le lien

• Pire cas () : temps maximal sur toutes les entrées de taille
• Meilleur cas () : temps minimal
• Cas moyen () : espérance sur une distribution des entrées

Exemple - Recherche linéaire :

• Pire cas : (élément absent)
• Meilleur cas : (premier élément)
• Cas moyen :

#Master TheoremCopier le lien

Pour les récurrences de type diviser pour régner :

où , :

1. Si :
2. Si :
3. Si :

Exemple - Tri fusion :

• Cas 2 :

#Complexité amortieCopier le lien

L'analyse amortie considère le coût moyen sur une séquence d'opérations plutôt que le pire cas isolé.

#Exemple : Tableau dynamiqueCopier le lien

Un tableau qui double sa capacité à chaque débordement :

• Pire cas d'un push : (recopie complète)
• Amorti :

Démonstration par méthode du potentiel :

Soit où = nombre d'éléments et = capacité.

Le coût amorti de chaque push est constant car le « crédit » accumulé paie les redimensionnements.

#Complexité spatialeCopier le lien

L'espace mémoire utilisé par un algorithme se mesure de la même façon :

• Espace auxiliaire : mémoire supplémentaire (hors entrée)
• Espace total : entrée + espace auxiliaire

Exemples :

• Tri fusion : espace auxiliaire
• Tri rapide : espace (pile de récursion)
• Tri par insertion sur place : espace auxiliaire

#ExercicesCopier le lien

1. Démontrez que .
2. Analysez la complexité amortie d'une table de hachage avec doublement de capacité.
3. Comparez l'impact mémoire de BFS vs DFS sur un graphe de densité variable.