1. Accueil
  2. TUTORIELS
  3. COMPLEXITE DES ALGORITHMES

COMPLEXITE DES ALGORITHMES

Pourquoi un programme qui marchait tres bien en test s'effondre-t-il en production ? Pourquoi un algorithme tient-il sur un million de donnees quand un autre, qui fait la meme chose, abandonne des le millier ? Ce cours repond a ces questions, sans mathematiques inutiles.

Ce que vous saurez faire a la fin

  • Lire un bout de code et annoncer sa complexite sans crayon.
  • Prevoir le temps d'execution sur dix fois plus de donnees, a partir d'une seule mesure.
  • Manier les notations O, Ω et Θ en sachant ce que chacune promet vraiment.
  • Analyser une fonction recursive, et appliquer le theoreme maitre.
  • Reconnaitre les couts caches des bibliotheques, ceux qui transforment un programme lineaire en programme quadratique sans qu'une ligne ne l'annonce.
  • Choisir entre deux algorithmes, et savoir quand l'optimisation n'en vaut pas la peine.

A qui s'adresse ce cours

A tout etudiant qui a deja ecrit des boucles et des fonctions. Aucune connaissance mathematique n'est requise au-dela du lycee : les quelques logarithmes qui apparaissent sont expliques quand ils arrivent.

Les exemples sont donnes en Python parce que c'est le langage le plus lisible pour cela, mais le raisonnement ne depend d'aucun langage : il vaut aussi bien pour du C, du Java ou du JavaScript.

Les six familles, d'un coup d'oeil

Six courbes de croissance comparees sur un meme repere : constante, logarithmique, lineaire, n log n, quadratique et exponentielle.

Tout le cours tient dans la lecture de ce graphique. Les deux courbes du bas ne montent pratiquement pas ; celle du haut quitte le cadre avant la neuvieme donnee. Comprendre pourquoi, et savoir dans laquelle de ces courbes se trouve votre programme, c'est l'essentiel du metier.

Les dix chapitres

Chapitre 1Pourquoi le chronomètre mentMesurer un programme au chronomètre donne des verdicts qui se contredisent d'une machine à l'autre. Première leçon de complexité : compter le travail plutôt que les secondes.Chapitre 2Compter les pas, pas les secondesComment traduire un bout de code en un compte d'opérations T(n) : ce qui coûte une unité, ce que coûte une boucle, et comment additionner le tout.Chapitre 3L'ordre de grandeur : jeter ce qui ne compte pasPourquoi 4n² + 2n + 7 se résume à « n² », pourquoi c'est légitime, et à partir de quel moment cette simplification devient dangereuse.Chapitre 4O, Ω et Θ : plafond, plancher, fourchetteLes trois notations de la complexité expliquées sans formalisme inutile : ce que chacune promet vraiment, et laquelle employer.Chapitre 5Les sept familles de croissanceDe O(1) à O(n!) : à quoi ressemble chaque famille, où on la rencontre, et combien de temps elle prend vraiment sur une machine réelle.Chapitre 6Lire la complexité dans un codeUne méthode pratique pour déterminer la complexité d'un programme en le regardant : les règles d'addition et de multiplication, les boucles qui divisent, et les pièges des bibliothèques.Chapitre 7Quand la fonction s'appelle elle-mêmeAnalyser une fonction récursive : écrire la récurrence, la dérouler en arbre d'appels, et appliquer le théorème maître pour conclure sans calcul.Chapitre 8Le pire, le meilleur, la moyenne et l'amortiUn même algorithme n'a pas une seule complexité. Pire cas, meilleur cas, cas moyen et coût amorti : quatre mesures, et laquelle croire.Chapitre 9La mémoire aussi se compteComplexité en espace : espace total, espace auxiliaire, pile d'appels, et l'échange qu'on peut toujours négocier entre temps et mémoire.Chapitre 10Optimiser sans se tromper de combatQuand l'analyse de complexité sert à décider : reconnaître la vraie cause d'une lenteur, savoir quand l'optimisation ne vaut rien, et les tableaux de référence à garder sous la main.

Pour aller plus loin

Pour prolonger ce cours : Algorithmes de graphes : parcours, chemins, arbres couvrants et flots, avec dix chapitres et des exercices corrigés.

Questions / Réponses

Aucune question. Soyez le premier à poser une question.
★ ★ ★ ★ ★
2 votes. Moyenne 5 sur 5.

Ajouter un commentaire

Anti-spam