Chapitre 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. 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 (2)1/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 ?