CHAPTER 1 Notions de complexité

Problem 1.0.1. Comparaison de la complexité de deux méthodes de tri. On a une liste que l’on veut trier, mettons 7, 8, 4, 2, 5, 9, 3, 5.

– Méthode 1 (tri sélection)

(1) On échange le premier élément avec le plus petit des éléments 2, 8, 4, 7, 5, 9, 3, 5

(2) On échange le deuxième élément avec le plus petit des éléments restants 2, 3, 4, 7, 5, 9, 8, 5

(3) …

(4) Au bout de k étapes, les k premiers éléments sont triés ; on échange alors le k + 1ème élément avec le plus petit des éléments restants.

(5) À la fin, la liste est triée : 2, 3, 4, 5, 5, 7, 8, 9.

– Méthode 2 (tri fusion)

(1) On groupe les éléments par paquets de deux, et on trie chacun de ces paquets : 7, 8, 2, 4, 5, 9, 3, 5.

(2) On groupe les éléments par paquets de quatres, et on trie chacun de ces paquets : 2, 4, 7, 8, 3, 5, 5, 9.

(3) …

(4) Au bout de k étapes, les paquets de 2^{k} éléments sont triés ; on les regroupe par paquets de 2^{k+1} que l’on trie.

(5) À la fin, tous les éléments sont dans le même paquet et sont triés : 2, 4, 7, 8, 3, 5, 5, 9. Quelle est la meilleure méthode ? Exercice 1. Évaluer au mieux la complexité des problèmes suivants :

(1) Calcul de n! ;

(2) Calcul du n-ième nombre de Fibonacci ;

(3) Recherche d’un mot dans un dictionnaire ;

(4) Calcul du pgcd de deux nombres ;

(5) Calcul du produit de deux matrices ;

(6) Calcul du déterminant d’une matrice ;

(7) Calcul du rang d’une matrice ;

(8) Inversion d’une matrice ;

(9) Calcul d’un vecteur x solution de Ax = b, où A est une matrice et b un vecteur ;

(10) Recherche du plus court chemin entre deux stations de métro à Paris ;

(11) Test de primalité de n.

(12) Calcul de la n-ième décimale de \sqrt{2} ;

(13) Calcul de l’inverse d’un nombre modulo 3 ;

(14) Recherche d’un échec et mat en 4 coups à partir d’une position donnée aux échecs.

(15) Problème du sac à dos : étant donné un ensemble d’objets d’épaisseur variable, et un sac à dos de hauteur donnée, peut-on remplir le sac à dos à bloc, sans déborder ?