Aller au contenu
Ludicademy
English
Thème Élan
ClairsSombres
S’inscrire

Fiche de révision : La complexité : compter les opérations, pas les secondes

L’essentiel de la leçon, ce qu’il faut retenir, les pièges et un petit test : une page à relire avant le contrôle.

Ludicademyludicademy.fr · apprendre en jouant, du CP à la Terminale
Fiche de révision · Logique · Tle · algorithmique

La complexité : compter les opérations, pas les secondes

Objectif : ce qui se passe quand les données deviennent grandes

L’essentiel

Mesurer un algorithme au chronomètre revient à mesurer une machine, un jour donné, sur un jeu d'essai donné. Changez de machine, la mesure change. La COMPLEXITÉ répond autrement : elle compte le NOMBRE D'OPÉRATIONS effectuées en fonction de la taille des données, notée n.

À retenir

  • La complexité compte les opérations selon la taille n, pas les secondes sur une machine
  • On garde l'ordre de grandeur : le terme dominant, sans ses constantes
  • Deux boucles imbriquées sur les mêmes données donnent du n au carré
  • Une complexité exponentielle est condamnée dès quelques dizaines de données

Le tableau à connaître

La familleLa notationQuand n doubleExemple typique
ConstanteO(1)Rien ne changeLire le premier élément d'une liste
LogarithmiqueO(log n)Une opération de plusLa recherche dichotomique
LinéaireO(n)Le temps doubleLe parcours complet d'une liste
QuadratiqueO(n²)Le temps quadrupleLe tri par sélection, deux boucles imbriquées
ExponentielleO(2 puissance n)Le temps est mis au carréL'essai de toutes les combinaisons

⚠ Attention, piège

  • Une complexité meilleure ne garantit pas un programme plus rapide SUR LES PETITES DONNÉES.

Exemples

  • Algorithme du tri par sélection. La boucle extérieure fait n moins 1 passes.

Le plan de la leçon

  1. Le chronomètre est un mauvais juge
  2. Les cinq familles qu'on rencontre
  3. Compter, sur un cas concret
  4. Ce que cela permet de décider avant d'écrire

Je me teste

  1. Un algorithme en O(n²) traite 1 000 éléments en 1 seconde. Et 10 000 ?

    1. Environ 1 seconde
    2. Environ 100 secondes
    3. Environ 10 secondes
  2. Que signifie O(log n) quand la taille des données double ?

    1. Le carré des opérations
    2. Deux fois plus d'opérations
    3. Une opération de plus environ

Le mot d’Oscar — Combien pour dix mille ?

Réponses : 1. B · 2. C

La leçon complète, ses exercices et ses jeux : ludicademy.fr/lecon/2414fiche de révision · usage libre en classe et à la maison

Toutes les fiches de révision : par matière et par classe · les fiches d’exercices : la bibliothèque.