#Complexité des algorithmesCopier le lien

Prérequis: boucles et récursivité, premières intuitions du « nombre d'opérations ».

Objectifs:

• Manipuler les notations O, Ω, Θ et o avec leurs définitions quantifiées.
• Analyser une boucle, une récurrence, un coût en espace, et savoir lequel mesure quoi.
• Appliquer le théorème maître aux récurrences des algorithmes diviser pour régner.
• Distinguer coût au pire, en moyenne et coût amorti, et choisir la bonne notion selon la question posée.

#Pourquoi des notations asymptotiquesCopier le lien

Comparer des algorithmes sur une machine donnée dépend du processeur, du compilateur, de la charge: deux mesures mettent rarement d'accord. L'analyse asymptotique décrit le taux de croissance du coût en fonction de la taille d'entrée n, à facteurs constants près. Elle prédit ce qui se passe quand n grandit, ce qui est précisément la question intéressante: pour n petit, tout est rapide; pour n grand, seule la classe de croissance compte.

Un algorithme en finit toujours par battre un algorithme en , quelle que soit la constante multiplicative du second, dès que n dépasse le seuil de croisement.

#Les trois notationsCopier le lien

Soit .

O (grand O), borne supérieure. si . Dire « l'algorithme est en O(g(n)) » signifie « ne croît pas plus vite que g, à constante près ».

Ω (grand oméga), borne inférieure. si . Ω sert surtout à deux choses: exprimer un pire cas (« le tri rapide tombe à Ω(n²) sur certaines entrées ») et les bornes inférieures de problèmes (aucun tri par comparaison ne fait mieux que ).

Θ (thêta), encadrement. : f et g croissent au même taux. C'est la réponse précise quand on l'a; écrire O là où on connaît Θ est correct mais perd de l'information.

o (petit o), borne stricte. si pour tout , f(n) < c·g(n) au-delà d'un rang: f est négligeable devant g. Exemple: mais (même ordre).

#Hiérarchie et ordres de grandeurCopier le lien

Pour n = 10⁶, à raison d'un milliard d'opérations par seconde:

La ligne de fracture est / contre : les classes polynomiales passent encore à n = 10⁶, les exponentielles s'effondrent dès n = 40 ou 50. C'est toute la distinction P / NP du chapitre suivant.

#Squelettes d'analyseCopier le lien

Trois motifs couvrent la quasi-totalité des boucles du module:

Balayage. Une boucle qui fait un travail constant par itération sur n éléments: . Exemple: calculer une somme.

Imbrication. Une boucle dans une boucle sur le même n: . Attention aux décalages: for i in range(n): for j in range(i, n): fait itérations, toujours quadratique.

Division. while n > 1: n //= 2 tourne fois: . Toute structure qui réduit le problème de moitié (recherche binaire, descente dans un arbre équilibré) hérite de ce coût.

Et le coût se compose: le tri d'abord, puis un balayage, donne ; l'addition garde la plus grande classe.

#Récurrences et théorème maîtreCopier le lien

Les algorithmes diviser pour régner (tri fusion, tri rapide, parcours d'arbres) ont un coût décrit par une récurrence: , où a est le nombre de sous-problèmes, n/b leur taille et f(n) le coût de découpe et de combinaison.

Théorème maître (forme usuelle). Posons :

1. Si pour un (f négligeable), alors : ce sont les feuilles qui paient.
2. Si , alors : chaque niveau coûte pareil, il y a log n niveaux.
3. Si avec la condition de régularité (f « nettement plus grande »), alors : c'est la racine qui paie.

Applications immédiates:

Attention à la dernière ligne: le théorème maître s'applique aux récurrences en n/b, pas en n − 1. Pour (tri rapide dégénéré), on déroule: .

#Trois méthodes pour résoudre une récurrenceCopier le lien

Le théorème maître n'est ni la seule méthode ni la plus générale. Trois techniques se complètent, et savoir laquelle s'applique fait gagner beaucoup de temps.

1. La méthode par substitution. On devine la forme de la solution, puis on prouve qu'elle convient par induction. C'est la méthode la plus générale, mais elle demande un candidat.

Exemple sur . On conjecture , c'est-à-dire pour une constante c bien choisie. En supposant l'inégalité vraie pour :

la dernière inégalité tenant dès que . La conjecture est donc vérifiée. Deux pièges classiques de la méthode: choisir la constante après coup (c'est légitime, mais il faut le dire), et oublier le cas de base (l'induction ne démarre que pour ; les petites valeurs se traitent à part, ce qui ne change pas l'ordre de grandeur).

2. L'arbre de récursion. On dessine l'arbre des appels, on calcule le coût de chaque niveau, puis on somme sur les niveaux. Cette méthode ne prouve rien à elle seule, mais elle fournit la conjecture que la substitution validera — c'est exactement son rôle dans le cours: « les arbres de récursion fournissent un moyen de générer une conjecture ».

Exemple sur , pour n puissance de 2:

Il y a niveaux, chacun coûtant cn, soit un total de . Le raisonnement de fond: doubler le nombre de nœuds divise exactement par deux le travail de chacun, donc le coût d'un niveau ne dépend pas de sa profondeur. C'est cette compensation exacte qui produit le facteur .

3. Le théorème maître. La méthode mécanique, applicable dès que la récurrence a la forme . Elle ne demande aucune conjecture et donne directement le résultat; en contrepartie elle ne couvre ni les récurrences en , ni celles dont les sous-problèmes sont de tailles inégales, ni les cas où la condition de régularité du cas 3 n'est pas satisfaite.

Comment choisir. Si la récurrence est de la forme , appliquer le théorème maître — c'est immédiat et sans risque. Sinon, dessiner l'arbre pour obtenir une conjecture, puis la valider par substitution. Ne jamais conclure sur un arbre de récursion seul: il donne une intuition, pas une preuve.

#Modèle de calculCopier le lien

Toute cette analyse suppose le modèle RAM (Random Access Machine): chaque opération élémentaire (arithmétique, comparaison, affectation, accès à une case mémoire) coûte un temps constant, indépendamment de la taille de la donnée; la mémoire est non bornée et à accès uniforme.

Le modèle a des limites à connaître:

• Les entiers machine sont bornés (64 bits usuellement); l'arithmétique sur des grands entiers sort du modèle et coûte selon leur taille.
• Le modèle ignore la hiérarchie mémoire (caches): deux algorithmes de même complexité peuvent différer d'un facteur important en pratique (cf. localité dans le module Structures de données).
• Un « O(1) » de Python (par exemple un dict.get) cache des constantes bien plus grandes qu'une addition machine.

C'est voulu: le modèle RAM isole l'effet de la taille d'entrée, et les écarts de constante se traitent par mesure, pas par asymptotique.

#Pire cas, meilleur cas, cas moyenCopier le lien

Trois fonctions distinctes, à ne jamais confondre:

• Pire cas : maximum du coût sur toutes les entrées de taille n. C'est la garantie contractuelle, celle qu'on exige d'un système interactif.
• Meilleur cas : minimum. Rarement utile seul, il sert à montrer qu'une borne inférieure ne peut pas être améliorée uniformément.
• Cas moyen : espérance du coût sur une distribution d'entrées (souvent: toutes les permutations équiprobables). Réaliste mais à condition de justifier la distribution.

Exemple canonique, la recherche séquentielle d'une clé présente dans un tableau de n éléments: pire cas n (clé en dernière position ou absente), meilleur cas 1, cas moyen sur position uniforme. Même classe pour le pire et la moyenne, mais constantes différentes; pour le tri rapide au contraire, pire cas contre en moyenne (chapitre Tris): la distinction y est cruciale.

#Analyse amortieCopier le lien

L'analyse amortie borne le coût moyen d'une opération sur une séquence, sans hypothèse probabiliste: c'est une garantie déterministe sur n'importe quelle suite d'opérations légales. Un coût amorti en O(1) signifie: toute séquence de n opérations coûte O(n) au total, même si certaines opérations isolées coûtent cher.

Trois méthodes, une même idée:

1. Agrégation: compter le coût total de la séquence et diviser.
2. Potentiel: définir sur l'état de la structure, croissant quand on « épargne »; le coût amorti d'une opération est son coût réel plus la variation de potentiel. La somme des coûts amortis majore le coût réel total.
3. Comptabilité: faire payer à chaque opération bon marché un crédit qui finance les opérations chères à venir.

Exemple du tableau dynamique. Un append sur un tableau plein déclenche un doublement (recopie de toutes les cases: O(n)) mais tous les autres append sont O(1). Une suite de n append depuis un tableau vide exécute au plus doublements et le coût total des recopies est : au total , donc O(1) amorti par append, alors que le pire cas isolé est Θ(n).

Par potentiel: où n est le remplissage et c la capacité. Un append sans doublement augmente Φ de 2 et coûte 1: coût amorti 3. Un append avec doublement a vidé le potentiel accumulé, coût amorti constant lui aussi. La lecture à retenir: le potentiel est l'épargne qui paie la prochaine vague de copies.

On retrouvera exactement ce raisonnement pour le redimensionnement des tables de hachage (module Structures de données).

#Complexité spatialeCopier le lien

L'espace se mesure comme le temps, en fonction de n, et se décompose:

• Espace auxiliaire: mémoire supplémentaire hors entrée et sortie. C'est presque toujours ce qu'on rapporte.
• Espace total: entrée comprise.

Exemples de référence: tri fusion auxiliaire (tableau temporaire de fusion); tri rapide (pile de récursion, en moyenne); tri par insertion (en place); tri par tas (en place, grâce à la représentation compacte du tas).

La récursivité coûte de l'espace: une récursion de profondeur p maintient p trames d'appel. Une implémentation itérative d'un parcours de graphe (BFS par file explicite) ou une mémoïsation par tableau peuvent réduire ou déplacer cette consommation; en programmation dynamique, l'optimisation d'espace (garder deux lignes au lieu de la table complète) est un exercice standard.

#ExercicesCopier le lien

1. Classer par ordre de croissance , , et pour n assez grand. Correction: . Argument: comparer les exposants ( domine tout polynôme d'exposant plus petit), et rappeler que pour tout .
2. Démontrer . Correction: encadrer par , prendre le log: , les deux bornes sont en . C'est le cœur de la borne inférieure des tris.
3. Analyser . Correction: ; , cas 1, . C'est la récurrence de la multiplication de Karatsuba.
4. Une pile avec pop qui, de temps en temps, compacte le tableau (recopie en O(n)). Donner un scénario où toute séquence reste O(1) amorti, et un contre-scénario où ce n'est plus vrai si la compaction a lieu trop souvent. Correction: si la compaction ne survient que quand le remplissage descend sous un quart de la capacité (stratégie de seuil, avec la capacité divisée par deux), le potentiel finance chaque compaction et l'amorti reste O(1); si la compaction est déclenchée à chaque pop, chaque opération déclenche une recopie O(n): aucune analyse amortie ne sauve le O(n) par opération.

#Mini-quizCopier le lien