Réponse: rien, ou presque. Le coût en temps et le coût en espace sont deux mesures indépendantes. Une borne supérieure sur l'espace n'impose aucune contrainte au temps: elle dit seulement que l'algorithme ne consomme pas plus de telle quantité de mémoire, pas ce qu'il fait de son temps.

Ce qui est vrai, en revanche. Une borne inférieure sur l'espace implique une borne inférieure sur le temps. Dans le modèle RAM, lire ou écrire une case mémoire est une opération élémentaire: si un algorithme doit écrire ou lire Ω(f(n)) cases distinctes, il exécute au moins Ω(f(n)) opérations. Autrement dit: espace Ω(f(n)) ⟹ temps Ω(f(n)). La réciproque est fausse, et une borne supérieure sur l'espace ne donne rien.

Pourquoi O(n) n'apprend rien. Quatre algorithmes du cours utilisent O(n) d'espace et ont des coûts en temps incomparables:

Le coût en temps est déterminé par la structure de l'algorithme (nombre de boucles imbriquées, divisions du problème), pas par la quantité de mémoire qu'il mobilise. Les deux se mesurent séparément.

Pourquoi O(log n) n'apprend pas davantage. Un espace logarithmique est compatible avec des temps très différents:

• Θ(log n): la recherche binaire, qui ne garde que deux bornes.
• Θ(n): un balayage de tableau n'utilisant qu'un compteur — l'énoncé le décrit en O(log n) parce que toute constante est dans O(log n), mais le temps reste linéaire.
• Θ(n log n): le tri rapide, dont la pile de récursion occupe Θ(log n) en moyenne.
• Θ(2^n): l'énumération exhaustive des sous-ensembles avec un tableau de bits de taille log n.

Ce qu'il faut répondre pour obtenir tous les points. Énoncer l'indépendance, la donner à voir par un contre-exemple chiffré (le tableau ci-dessus suffit), puis mentionner la seule implication valide — celle qui va d'une borne inférieure d'espace vers une borne inférieure de temps. C'est le point de méthode de l'exercice: une borne supérieure sur une ressource ne contraint pas l'autre ressource.

Définition. Un tri est stable si deux éléments de même clé apparaissent dans le tableau de sortie dans le même ordre relatif que dans le tableau d'entrée. Autrement dit: si x précède y dans l'entrée et que x et y ont la même clé, alors x précède y dans la sortie.

Pourquoi cela compte. La stabilité n'a d'intérêt que parce qu'un tri porte presque toujours sur des enregistrements, pas sur des clés nues. Un tri d'étudiants par nom de famille ne doit pas mélanger l'ordre alphabétique des prénoms à l'intérieur d'une même famille. Deux usages concrets:

• Trier sur plusieurs clés par passes successives. Pour trier par (nom, prénom), on trie d'abord par prénom, puis par nom avec un tri stable: la seconde passe ne détruit pas l'ordre établi par la première à l'intérieur des groupes de même nom. Avec un tri instable, le résultat est imprévisible.
• Le tri par base. Chaque passe trie sur un chiffre; la stabilité est la condition même de la correction de l'algorithme (voir le chapitre sur les tris).

Quels tris sont stables, et par quel mécanisme.

Contre-exemple pour le tri par sélection. Soit A = [3a, 3b, 1] où 3a et 3b sont deux éléments de même clé, 3a apparaissant avant 3b. La première passe cherche le minimum de tout le tableau: c'est 1, en position 3. Elle l'échange avec l'élément en position 1:

1[3a, 3b, 1]  →  [1, 3b, 3a]

Les deux éléments de clé 3 ont échangé leur ordre relatif: le tri par sélection n'est pas stable. Le mécanisme fautif est l'échange à distance: contrairement à l'insertion, qui ne déplace les éléments que d'une case et uniquement s'ils sont strictement plus grands, la sélection fait voyager un élément sur toute la longueur de la zone non triée.

Conséquence pratique. Un tri stable coûte-t-il plus cher? Non: insertion, fusion et comptage sont stables sans surcoût. À l'inverse, rendre stable le tri par sélection ou le tri par tas demande de la mémoire supplémentaire (stocker l'indice d'origine et trier sur le couple (clé, indice)), ce qui les fait sortir de la classe « en place ». La stabilité n'est donc pas un luxe coûteux: c'est une propriété gratuite de certains algorithmes et inaccessible à d'autres.

La réponse attendue n'est pas « on prend le plus rapide », mais une méthode de décision, hiérarchisée du plus contraignant au plus accessoire.

1. La contrainte dure: la classe asymptotique du pire cas. C'est elle qui décide si le programme est utilisable. Un algorithme en Θ(n log n) et un algorithme en Θ(n²) sont tous deux corrects, mais pour n = 10⁶ le second est inutilisable quelle que soit la machine. Le pire cas est la seule garantie contractuelle: sur un système interactif ou en traitement par lots, c'est lui qu'on annonce.

2. Le cas moyen, si la distribution d'entrées est connue et justifiée. Le tri rapide est en Θ(n²) au pire et Θ(n log n) en moyenne; il est excellent si les entrées adverses ne se présentent pas (ou si le pivot est aléatoire). Encore faut-il pouvoir énoncer la distribution, sinon la moyenne n'est qu'une espérance sur un modèle qui ne décrit pas les données réelles.

3. Les ressources autres que le temps: l'espace. Le tri fusion est en Θ(n) d'espace auxiliaire, le tri par tas en Θ(1). Sur un système embarqué, ce critère peut primer sur la vitesse. Un algorithme en Θ(n log n) qui demande de doubler la mémoire peut être écarté au profit d'un Θ(n log n) en place.

4. Les constantes et le comportement matériel. À classe égale, les constantes et la localité mémoire décident. Le tri par tas et le tri rapide sont tous deux en Θ(n log n) en moyenne, mais le tri rapide est typiquement deux à trois fois plus rapide sur des tableaux en mémoire, parce qu'il accède séquentiellement à la mémoire et que le tri par tas saute entre les niveaux de l'arbre. Deux algorithmes de même complexité peuvent donc différer d'un facteur important, que l'asymptotique ne montre pas.

5. Les propriétés structurelles: stabilité, déterminisme, garantie. Un tri stable est requis pour un tri multi-clés; un algorithme déterministe est requis si le résultat doit être reproductible; une garantie de pire cas est requise si une échéance est contractuelle.

6. Le coût de mise en œuvre et le risque. À qualité de résultat égale, l'algorithme le plus simple est le plus sûr: moins de code, moins de cas limites, plus facile à tester. Un algorithme subtil qu'on implémente mal perd contre un algorithme simple bien implémenté.

La méthode concrète, en pratique. On ne tranche pas au feeling: on compte les opérations élémentaires (comparaisons, écritures) plutôt que de chronométrer, car le comptage est déterministe et indépendant de la machine; puis on mesure sur des données représentatives, car les constantes et le cache ne se déduisent pas de l'analyse. Les deux résultats se croisent: la classe asymptotique prédit le comportement pour n grand, la mesure donne le seuil de bascule — c'est exactement l'exercice du tri hybride fusion + insertion, où l'on choisit expérimentalement la taille sous laquelle l'insertion gagne.

Ce qui serait une mauvaise réponse. « Je prends le plus rapide » sans préciser sur quoi (quel cas? quelle taille? quelle machine?); ou « je prends celui qui a la plus petite complexité » sans vérifier les constantes, alors qu'en dessous du seuil de croisement le plus lent asymptotiquement est le plus rapide en pratique.

1INSERTION-SORT-0(A, n)21  pour i = 1 à n − 1                       // A[0] est déjà trié à lui seul32      clé = A[i]43      j = i − 154      tant que j ≥ 0 et A[j] > clé         // attention: j ≥ 0, et non j > 065          A[j + 1] = A[j]76          j = j − 187      A[j + 1] = clé

Le piège, et il est unique. Avec une numérotation à partir de 1, la condition d'arrêt du tant que est j > 0: l'indice 0 sert de sentinelle naturelle, et la boucle s'arrête d'elle-même quand j l'atteint. Avec une numérotation à partir de 0, la borne change: il faut j ≥ 0. Écrire j > 0 par recopie laisse la position 0 non examinée: un élément plus petit que tout ce qui le précède ne pourra jamais être inséré en tête, et le tableau restera faux — silencieusement, sans erreur d'exécution.

Ce qui ne change pas. L'invariant, la structure de l'algorithme, la stabilité (la comparaison reste stricte), les coûts: Θ(n²) au pire, Θ(n) au mieux, O(1) d'espace. Seule l'écriture des bornes change.

Exemple d'exécution sur A = [4, 2, 7, 1]:

L'itération i = 1 est celle qui teste la nouvelle borne: j part de 0, effectue le décalage, puis descend à −1. Avec la condition j > 0 recopiée de la version 1-indexée, cette itération n'aurait rien fait et le tableau serait resté [4, 2, 7, 1].

Remarque de portage. Ce décalage d'indice est la première source d'erreur quand on transpose un algorithme du pseudocode du cours vers un langage à indices commençant à 0 (C, Python, Java). Deux parades: écrire les bornes explicitement dans le commentaire d'en-tête de la fonction, ou allouer une case supplémentaire en tête et ignorer l'indice 0 — cette seconde solution, courante en C, rend la traduction littérale.

1SELECTION-SORT(A, n)21  pour i = 1 à n − 132      min = i43      pour j = i + 1 à n54          si A[j] < A[min]65              min = j                       // mémoriser l'indice du plus petit, pas sa valeur76      si min ≠ i87          échanger A[i] et A[min]

Invariant de boucle. Au début de chaque itération de la boucle externe (indice i), le sous-tableau A[1..i−1] contient les i − 1 plus petits éléments de l'entrée, rangés en ordre trié et à leur position définitive.

• Initialisation. i = 1: A[1..0] est vide, l'invariant est vrai par vacuité.
• Maintenance. La boucle interne détermine l'indice min du plus petit élément de A[i..n]. Comme A[1..i−1] contient déjà les i − 1 plus petits éléments, tous inférieurs ou égaux à tout élément de A[i..n], l'échange place le i-ième plus petit élément en position i. Après l'échange, A[1..i] contient les i plus petits éléments, triés.
• Terminaison. À i = n, A[1..n−1] contient les n − 1 plus petits éléments triés; le dernier élément est donc nécessairement à sa place, et A[1..n] est trié.

Estimation du temps d'exécution. Le nombre de comparaisons de la ligne 4 est exactement

1Σ_{i=1}^{n−1} (n − i) = (n − 1) + (n − 2) + … + 1 = n(n − 1)/2

C'est une fonction du seul n: la boucle interne parcourt toujours tout le reste du tableau, quel que soit le contenu. Le tri par sélection effectue donc exactement n(n − 1)/2 comparaisons dans tous les cas — meilleur cas, cas moyen et pire cas confondus. Il n'a aucun meilleur cas: une entrée déjà triée ne lui fait gagner aucune comparaison. Le coût est Θ(n²) uniformément, et les échanges, au plus n − 1, sont négligeables devant.

Le point qui distingue le tri par sélection. C'est le tri à retenir quand l'écriture est très coûteuse et la lecture bon marché: il n'effectue au plus que n − 1 échanges, contre Θ(n²) pour le tri par insertion ou le tri à bulles. Sur une mémoire flash, où chaque écriture use la cellule, ou sur des structures dont la copie est lourde, ce critère prime sur le nombre de comparaisons. C'est aussi le seul des tris quadratiques dont le coût est totalement insensible à l'ordre de l'entrée.

En revanche, il n'est pas stable. Voir l'exercice 2 pour le contre-exemple [3a, 3b, 1], où la première passe échange le minimum avec la position 1 et inverse l'ordre relatif des deux éléments de clé 3.

Rappel de la procédure, dans la forme du cours: MERGE(A, p, q, r) fusionne les deux sous-tableaux triés A[p..q] et A[q+1..r]. Elle les recopie dans deux tableaux L[1..n1] et R[1..n2], ajoute une sentinelle ∞ au bout de chacun, puis recopie dans A[p..r] en prenant toujours la plus petite des deux têtes:

1MERGE(A, p, q, r)21  n1 = q − p + 1 ;  n2 = r − q32  L[1..n1+1] et R[1..n2+1] : L[i] = A[p+i−1], R[j] = A[q+j]43  L[n1+1] = ∞ ;  R[n2+1] = ∞54  i = 1 ;  j = 165  pour k = p à r76      si L[i] ≤ R[j]87          A[k] = L[i] ;  i = i + 198      sinon109          A[k] = R[j] ;  j = j + 1

Invariant. Au début de chaque itération de la boucle pour k, le sous-tableau A[p..k−1] contient les k − p plus petits éléments de L[1..n1+1] ∪ R[1..n2+1], en ordre trié. De plus, L[i] et R[j] sont les plus petits éléments de leurs tableaux respectifs qui n'ont pas encore été recopiés dans A.

Initialisation. Avant la première itération, k = p, donc A[p..k−1] est vide: elle contient bien les k − p = 0 plus petits éléments, et la propriété d'ordre est vide. Par ailleurs i = j = 1, donc L[1] et R[1] sont les plus petits éléments non recopiés de chaque tableau. L'invariant est vérifié.

Maintenance. Supposons l'invariant vrai avant l'itération d'indice k. Deux cas, selon le test de la ligne 6.

• Si L[i] ≤ R[j]: L[i] est le plus petit des deux plus petits éléments restants, donc le plus petit élément non recopié de L ∪ R. Comme A[p..k−1] contient déjà les k − p plus petits éléments et que L[i] est supérieur ou égal à A[k−1] (les éléments déjà recopiés sont plus petits), écrire L[i] en A[k] fait que A[p..k] contient les k − p + 1 plus petits éléments, en ordre trié. Incrémenter i rétablit la seconde partie de l'invariant.
• Si L[i] > R[j]: le raisonnement est symétrique, avec R[j] et j.

Terminaison. La boucle s'arrête quand k = r + 1. En substituant dans l'invariant: A[p..r] contient les (r + 1) − p = r − p + 1 plus petits éléments de L ∪ R, en ordre trié. Or L et R contiennent à eux deux exactement les éléments initialement dans A[p..r] — la copie des lignes 2 n'en perd ni n'en duplique aucun. Donc A[p..r] contient tous les éléments de départ, triés. La procédure est correcte.

Rôle des sentinelles. Elles ne servent qu'à la terminaison de la boucle: dès qu'un des deux tableaux est épuisé, sa sentinelle ∞ perd tous les tests et c'est l'autre tableau qui se déverse entièrement. Sans elles, il faudrait tester à chaque itération si i et j sont encore dans les bornes, et ajouter deux boucles de vidage après la boucle principale. Le coût est inchangé — deux cases de plus — mais le code perd deux cas de bord, et les cas de bord sont là où les bugs se logent.

Coût. La boucle s'exécute exactement r − p + 1 fois, soit n itérations pour un segment de taille n: chaque itération recopie un élément, et chaque élément est recopié une fois. Le coût de la fusion est donc Θ(n), indépendamment de la répartition des valeurs.

Idée. On partitionne en trois régions au lieu de deux: à gauche les éléments strictement inférieurs au pivot, au milieu ceux qui lui sont égaux, à droite ceux qui lui sont strictement supérieurs. Deux frontières mobiles suffisent: lt marque la fin de la zone des plus petits, gt le début de la zone des plus grands, et i explore entre les deux.

1PARTITION1(A, p, r)21  x = A[r]                          // pivot, valeur conservée dans x32  lt = p                            // A[p..lt−1] < x43  i = p                             // A[lt..i−1] = x54  gt = r − 1                        // A[gt+1..r−1] > x65  tant que i ≤ gt76      si A[i] < x87          échanger A[lt] et A[i]98          lt = lt + 1 ;  i = i + 1109      sinon si A[i] > x1110         échanger A[i] et A[gt]1211         gt = gt − 1               // i ne bouge PAS: l'élément venu de gt est inconnu1312     sinon1413         i = i + 1                 // A[i] = x: il rejoint la zone du milieu

Justification de l'invariant. À chaque tour: A[p..lt−1] ne contient que des éléments inférieurs à x; A[lt..i−1] ne contient que des éléments égaux à x; A[i..gt] n'a pas encore été examiné; A[gt+1..r−1] ne contient que des éléments supérieurs à x. Les trois cas de la boucle rétablissent cet invariant:

• A[i] < x: l'échange place en A[lt] un élément inférieur à x et en A[i] l'ancien A[lt], qui valait x (par invariant). Après incrémentation de lt et de i, les deux zones ont grandi d'une case.
• A[i] > x: l'échange place en A[gt] un élément supérieur à x et en A[i] l'ancien A[gt], dont on ne sait rien — d'où le fait que i ne bouge pas. Décrémenter gt suffit.
• A[i] = x: il suffit d'incrémenter i pour que l'élément rejoigne la zone du milieu.

Terminaison de la boucle. gt − i + 1 (le nombre d'éléments non examinés) décroît strictement à chaque itération: de 1 dans les premier et troisième cas, de 1 aussi dans le deuxième cas (où i est inchangé mais gt décroît). La boucle s'arrête donc en au plus r − p itérations.

La ligne 15. À la sortie, A[r] = x n'a jamais été touché (la boucle s'arrête à gt ≤ r − 1). L'échanger avec A[gt+1], qui contenait un élément supérieur à x, place le pivot en tête du bloc des égaux et repousse l'élément supérieur à la fin. Après cet échange: A[lt..gt+1] ne contient que des éléments égaux à x, A[p..lt−1] que des inférieurs, A[gt+2..r] que des supérieurs. On renvoie (q, t) = (lt, gt+1), et l'on a bien p ≤ q ≤ t ≤ r.

Le tri rapide correspondant.

1QUICKSORT1(A, p, r)21  si p < r32      (q, t) = PARTITION1(A, p, r)43      QUICKSORT1(A, p, q − 1)54      QUICKSORT1(A, t + 1, r)       // A[q..t] est définitivement en place: on ne le trie pas

Pourquoi c'est un progrès, et pas seulement une variante. Dans la version à deux voies, un tableau dont toutes les clés sont égales est le pire cas absolu: chaque partitionnement isole un seul élément et le coût monte à Θ(n²). Avec PARTITION1, toutes les clés égales au pivot sont regroupées et jamais réexaminées: sur n clés identiques, l'algorithme fait un seul partitionnement en Θ(n) puis deux appels sur des sous-tableaux vides. Le coût passe de Θ(n²) à Θ(n). C'est le cas des clés à faible diversité (notes sur 20, codes de département, indicateurs booléens), fréquent en pratique, et c'est la raison d'être de cette variante.

Déroulement sur A = [4, 2, 4, 4, 1, 4], p = 0, r = 5. Le pivot est x = A[5] = 4.

La ligne 15 échange A[gt+1] = A[5] avec A[r] = A[5]: aucun changement. On renvoie (q, t) = (2, 5). Vérification: A[2..5] = [4, 4, 4, 4] sont tous égaux à A[q] = 4; A[0..1] = [2, 1] sont tous inférieurs à 4; A[6..5] est vide. Les quatre clés égales au pivot sont sorties de la récursion, qui ne porte plus que sur [2, 1].

Lecture des définitions. Posons lo = min(a, b) et hi = max(a, b). Alors

1A1 = { x : x < lo }        A2 = { x : lo ≤ x ≤ hi }        A3 = { x : x > hi }

Les trois ensembles sont disjoints et leur union est A tout entier: c'est donc un partitionnement à trois voies, mais avec deux seuils au lieu d'un seul pivot. Le bloc du milieu est un intervalle, pas un singleton.

Partitionnement.

1PARTITION2(A, p, r, a, b)21  lo = min(a, b) ;  hi = max(a, b)32  i = p ;  j = p ;  k = r43  tant que j ≤ k54      si A[j] < lo65          échanger A[i] et A[j]76          i = i + 1 ;  j = j + 187      sinon si A[j] > hi98          échanger A[j] et A[k]109          k = k − 1                      // j ne bouge pas: l'élément venu de k est inconnu1110     sinon1211         j = j + 11312 renvoyer (i − 1, k + 1)               // A1 = A[p..i−1], A2 = A[i..k], A3 = A[k+1..r]

Invariant. À chaque tour: A[p..i−1] ne contient que des éléments inférieurs à lo; A[i..j−1] ne contient que des éléments dans l'intervalle [lo, hi]; A[k+1..r] ne contient que des éléments supérieurs à hi; A[j..k] n'a pas encore été examiné. Les trois branches rétablissent l'invariant, exactement comme dans l'exercice précédent. La boucle se termine car k − j + 1 décroît strictement à chaque itération.

Le tri rapide à deux pivots.

1QUICKSORT2(A, p, r)21  si p < r32      a = A[p] ;  b = A[r]43      si a > b alors échanger A[p] et A[r] ;  échanger a et b54      (q1, q2) = PARTITION2(A, p, r, a, b)65      QUICKSORT2(A, p, q1)                    // trier A1 = A[p..q1]76      QUICKSORT(A, q1 + 1, q2 − 1)            // trier A2 = A[q1+1..q2−1]87      QUICKSORT2(A, q2, r)                    // trier A3 = A[q2..r]

Les lignes 2 et 3 choisissent a = A[p] et b = A[r] parmi les éléments du tableau, et les ordonnent: les définitions de A1 et A3 étant symétriques en a et b, l'ordre n'a pas d'importance pour la validité, mais il fixe lo et hi et évite un test à chaque comparaison.

Pourquoi la ligne 6 utilise le tri rapide ordinaire. Après le partitionnement, les éléments de A2 sont tous dans [lo, hi]; rien ne garantit qu'ils prennent plus d'une valeur. Si tous valent lo, relancer QUICKSORT2 sur A2 avec deux pivots tirés de A2 reproduirait exactement la même partition, sans réduire le sous-tableau: la récursion ne terminerait pas. Le tri rapide ordinaire, lui, place toujours son pivot à sa position définitive et progresse dans tous les cas. C'est le même raisonnement que dans l'exercice précédent, où le bloc des égaux était simplement exclu de la récursion.

Déroulement sur A = [7, 2, 9, 4, 1, 8, 3], p = 0, r = 6. La ligne 3 échange A[0] et A[6], d'où a = 3, b = 7 et A = [3, 2, 9, 4, 1, 8, 7].

On renvoie (q1, q2) = (i − 1, k + 1) = (1, 5). Vérification: A1 = A[0..1] = [2, 1], tous inférieurs à 3; A2 = A[2..4] = [7, 4, 3], tous dans [3, 7]; A3 = A[5..6] = [8, 9], tous supérieurs à 7. La récursion porte ensuite sur A1 (deux éléments, trivial), A2 (tri rapide ordinaire) et A3 (deux éléments, trivial).

Ce que cette variante apporte. Elle réduit le nombre de comparaisons et d'échanges par élément sur des données réelles, parce qu'un seul passage partitionne autour de deux valeurs au lieu d'une. C'est la version utilisée par la bibliothèque standard de Java pour trier les tableaux de primitives. Elle ne change pas la classe asymptotique: Θ(n log n) en moyenne, Θ(n²) dans le pire cas — le choix de a et b aux extrémités reste vulnérable à une entrée déjà triée, et les mêmes parades s'appliquent (choix aléatoire des pivots, médiane de trois).

Ce que fait l'algorithme. Il essaie les diviseurs k dans l'ordre croissant à partir de 2. Quand k divise N, il l'enregistre et divise N par k — sans incrémenter k, ce qui permet d'extraire les facteurs répétés (par exemple 2 trois fois de suite pour N = 8). Sinon il passe au diviseur suivant. C'est l'algorithme de division par essais: il produit la liste des facteurs premiers de N avec leur multiplicité, dans l'ordre croissant.

Complexité en temps. La variable k part de 2 et n'est jamais décrémentée. Elle est incrémentée d'exactement 1 à chaque fois que k ne divise pas N, et N décroît à chaque division. La boucle s'arrête quand k ≥ N. Le nombre total d'itérations est donc au plus N − 2: dans le pire cas (par exemple N premier, où k parcourt toutes les valeurs de 2 à N − 1 sans jamais diviser), la boucle s'exécute N − 2 fois. Chaque itération coûte Θ(1) opérations arithmétiques sur des entiers de taille comparable à N. Le temps est donc Θ(N) dans le pire cas.

Est-il polynomial? Non. C'est le point de l'exercice, et il faut le dire précisément. La complexité d'un algorithme se mesure en fonction de la taille de l'entrée, et non de sa valeur. Un entier N s'encode sur b = ⌊log₂ N⌋ + 1 bits: la taille de l'entrée est b, pas N. Or

1N = 2^(log₂ N) = 2^(Θ(b))

Le temps d'exécution Θ(N) est donc exponentiel en la taille de l'entrée: doubler le nombre de bits de N élève le temps au carré. Pour un entier de 256 bits (un nombre RSA modeste), le pire cas demande de l'ordre de 2²⁵⁶ itérations — jamais atteignable.

Un algorithme dont le coût est polynomial en la valeur de l'entrée, mais exponentiel en sa taille, est dit pseudo-polynomial. La division par essais en est l'exemple canonique, comme l'algorithme de programmation dynamique pour le problème du sac à dos. Ce n'est pas une bizarrerie théorique: c'est exactement ce qui rend la factorisation difficile, et donc ce qui protège RSA. Aucun algorithme polynomial en la taille de l'entrée n'est connu pour la factorisation entière; le meilleur algorithme classique (crible généralisé sur les corps de nombres) est sous-exponentiel.

Complexité en espace. La liste L reçoit un élément à chaque division réussie. Le nombre de divisions est le nombre de facteurs premiers de N comptés avec multiplicité, majoré par log₂ N (chaque facteur vaut au moins 2). Les autres variables (k, N) sont des entiers d'au plus b bits. L'espace est donc Θ(log N), c'est-à-dire linéaire en la taille de l'entrée — polynomial. Ironie de l'exercice: IMPOSTEUR est économe en mémoire et catastrophique en temps. C'est un rappel que les deux ressources se mesurent séparément.

Ce qu'il faudrait pour le rendre meilleur. Deux améliorations classiques, sans changer la classe asymptotique: ne tester que k jusqu'à √N (au-delà, tout diviseur restant est premier), et ne tester que les diviseurs impairs après 2. Le coût passe de Θ(N) à Θ(√N) — toujours exponentiel en la taille de l'entrée, mais avec un exposant divisé par deux. La complexité en espace, elle, ne change pas.

Version naïve. Deux boucles imbriquées testant toutes les paires: Θ(n·m) comparaisons. Correct, mais coûteux: pour n = m = 10⁶, cela fait 10¹² tests.

Version par tri et recherche binaire. On trie S1, puis, pour chaque élément de S2, on cherche s − y dans S1 par recherche binaire. S1 étant trié, la recherche est en Θ(log n).

12SUM(S1, S2, s)21  T = TRI-FUSION(S1)                     // Θ(n log n)32  pour j = 1 à m                         // m itérations43      si RECHERCHE-BINAIRE(T, s − S2[j]) ≠ NIL54          renvoyer VRAI                  // Θ(log n) par recherche65  renvoyer FAUX

Complexité. Θ(n log n) pour le tri, puis m recherches binaires en Θ(log n) chacune, soit Θ(m log n). Total:

1Θ(n log n + m log n)

Avec l'hypothèse de l'énoncé n ≥ m, c'est Θ(n log n): le terme dominant est le tri de S1. On peut aussi trier les deux ensembles et utiliser deux index avançant l'un vers l'autre (un depuis le début de S1, l'autre depuis la fin de S2), ce qui donne Θ(n log n + m log m) puis Θ(n + m) pour la recherche: même classe, mais un balayage linéaire au lieu de m recherches logarithmiques — légèrement meilleur en pratique.

Correction de l'algorithme. S'il existe xi ∈ S1 et yj ∈ S2 avec xi + yj = s, alors en traitant yj à l'étape 2, la valeur cherchée est s − yj = xi, présente dans T puisque T est une permutation de S1: la recherche binaire la trouve et l'algorithme répond VRAI. Réciproquement, tout succès de la ligne 3 exhibe un indice i tel que T[i] = s − S2[j], donc un couple (T[i], S2[j]) de somme s. La réponse est donc correcte dans les deux sens.

Deux détails à ne pas manquer.

• Duplicats et indices. Si la recherche binaire renvoie un indice correspondant à l'élément yj lui-même (cas où les deux ensembles se recouvrent), il faut s'assurer que le couple exhibé est bien formé. Dans l'énoncé, S1 et S2 sont deux ensembles distincts: le cas ne se pose pas, mais il se poserait dans la variante « existe-t-il deux éléments de S de somme s? », où le couple (a, a) n'est valide que si a apparaît deux fois.
• La contrainte n ≥ m. Elle justifie le choix de trier S1 et de chercher depuis S2: on paie le tri sur le plus grand et la recherche sur le plus petit. Si m > n, il faut inverser les rôles pour obtenir Θ(m log m + n log m).

Variante en temps attendu linéaire. Si l'on dispose d'une table de hachage, on y insère les n éléments de S1 (Θ(n) attendu), puis on teste les m éléments de S2 par RECHERCHER(s − y) (Θ(m) attendu). Le coût passe à Θ(n + m) attendu, au prix de Θ(n) d'espace et de la dépendance à la qualité de la fonction de hachage. Le tri garde l'avantage de la garantie de pire cas et de l'espace Θ(n) maîtrisé.

Structure de la solution. L'algorithme procède en trois temps: (1) un premier parcours de la liste pour recenser les documents distincts et leur attribuer un indice, via le dictionnaire; (2) l'initialisation de la matrice à 100 partout, puis 0 sur la diagonale; (3) un second parcours pour écrire les distances des couples réellement présents dans le rapport, en remplissant deux cases à chaque fois (symétrie).

1MATRICE-DISTANCES(L)21  D = DICO vide                                  // document → numéro de ligne et de colonne32  n = 043  pour chaque nœud p de la liste L               // premier parcours: recenser les documents54      c = p.DONNEE65      si RECHERCHER(D, c.L) == NIL76          n = n + 1 ;  ASSOCIER(D, n, c.L)87      si RECHERCHER(D, c.R) == NIL98          n = n + 1 ;  ASSOCIER(D, n, c.R)109  M = matrice n × n initialisée à 1001110 pour i = 1 à n1211     M[i][i] = 0                                 // tout document est à distance nulle de lui-même1312 pour chaque nœud p de la liste L               // second parcours: remplir les distances connues1413     c = p.DONNEE

Correction. Le premier parcours garantit que tout document apparaissant dans au moins une ligne du rapport reçoit un indice, et un seul: le test RECHERCHER(D, c.L) == NIL évite de numéroter deux fois le même document. La matrice est donc carrée de côté n, le nombre exact de documents comparés au moins une fois. L'initialisation à 100 code le cas « les deux documents n'ont aucune phrase en commun », qui correspond à l'absence de ligne dans le rapport. Le second parcours écrit dist(L, R) dans les deux cases symétriques, ce qui réalise l'égalité D[i][j] = D[j][i] demandée. Un couple (L, R) absent du rapport n'est jamais écrit et conserve 100; la diagonale reste à 0. Les hypothèses de l'énoncé sont respectées: un document garde le même indice en ligne et en colonne, puisque l'indice est stocké dans D et relu tel quel.

Question 2: coût en temps. Notons m le nombre de nœuds de la liste (de lignes du rapport) et n le nombre de documents distincts.

• Premier parcours: m itérations, chacune avec deux RECHERCHER et au plus deux ASSOCIER, tous en O(1): Θ(m).
• Initialisation de la matrice: n² cases à écrire: Θ(n²).
• Second parcours: m itérations, chacune avec deux RECHERCHER et deux écritures, en O(1): Θ(m).

Coût total: Θ(m + n²), dominé par l'initialisation de la matrice. C'est incompressible dans cette représentation: une matrice n × n occupe n² cases, et il faut bien les écrire une fois.

Question 2, le point qui compte. La liste du rapport peut être courte alors que le nombre de documents est grand, et c'est le terme n² qui explose: avec 10 000 documents comparés au moins une fois, la matrice occupe 10⁸ cases, soit plusieurs centaines de mégaoctets pour des réels en double précision — même si le rapport ne contient qu'une centaine de lignes. Le coût en espace est Θ(n²), et c'est lui qui limite l'usage. Une représentation creuse (dictionnaire indexé par le couple (i, j), ou listes d'adjacence) ramènerait le coût à Θ(m), au prix d'un accès D[i][j] non constant. Choisir la représentation matricielle, c'est décider que le nombre de documents restera petit; l'énoncé impose la matrice, mais il faut savoir ce qu'elle coûte.

Question 3: affichage.

1AFFICHER-MATRICE(M, D, n)21  afficher n32  pour i = 1 à n43      afficher CLES(D)[i]                        // nom du i-ième document54      pour j = 1 à n65          afficher M[i][j]                       // les n distances, sur la même ligne76      aller à la ligne

Coût: Θ(n) pour les en-têtes et les passages à la ligne, Θ(n²) pour les n² valeurs affichées. Total Θ(n²), incompressible puisque la sortie elle-même est de taille n². C'est le cas d'école où le coût de l'algorithme est inévitablement au moins égal à la taille de sa sortie: aucune astuce ne peut afficher n² nombres plus vite que n² opérations.