Big O, Pseudo-code et Mesure de Performance
Utilisez les flèches, cliquez ou glissez pour naviguer
1. Écrire du pseudo-code
DĂ©crire une solution avant de coder
2. Identifier la complexité
O(1), O(n), O(n²)
3. Comprendre O(n) vs O(n²)
Différence concrète de performance
4. Analyser des fonctions existantes
Calculer la complexité
Qu'est-ce qu'un algorithme ?
Exemples du quotidien : recette, GPS, dictionnaire
Le pseudo-code
DĂ©crire une solution avant de coder
La notion de complexité
Combien d'opérations pour N éléments ?
O(1), O(n), O(n²)
Accès index, parcours, boucles imbriquées
Exercice en live
Compter les opérations d'un algorithme
Une suite d'étapes pour résoudre un problème
Comme une recette de cuisine, mais pour l'ordinateur
cookbook
Recette de cuisine
1. Préparer les ingrédients
2. MĂ©langer
3. Cuire 30 min
4. Servir
navigation
GPS
1. Position actuelle
2. Destination
3. Calculer itinéraire
4. Guider Ă©tape par Ă©tape
book-open
Dictionnaire
1. Ouvrir au milieu
2. Comparer la lettre
3. Aller avant/arrière
4. Répéter jusqu'à trouver
Chaque étape est précise et dans un ordre logique
DĂ©crire une solution avant de coder
Un langage simple et universel
Compréhensible par tous les programmeurs
Sans pseudo-code
Coder directement sans réfléchir
Se perdre dans les détails
Recommencer plusieurs fois
Temps perdu!
Avec pseudo-code
Réfléchir à la logique d'abord
Voir les problèmes avant de coder
Coder une fois correctement
Gain de temps!
Comme un plan de maison avant de construire
// Pseudo-code
FONCTION
trouverMax(tableau)max = tableau[0]
POUR CHAQUE
nombre DANS tableauSI
nombre > maxmax = nombre
FIN SI
FIN POUR
RETOURNER
maxFIN FONCTION
Pas de syntaxe compliquée, juste la logique!
// Pseudo-code
FONCTION
trouverMax(tableau)max = tableau[0]
POUR CHAQUE
n DANS tableauSI
n > maxmax = n
RETOURNER
max// JavaScript
function trouverMax(tableau) {
let max = tableau[0];
for (let n of tableau) {
if (n > max) {
max = n;
}
}
return max;
}
La traduction est directe et naturelle!
Combien d'opérations pour N éléments ?
Mesurer l'efficacité d'un algorithme
Sans se soucier des détails d'implémentation
Un même problème peut avoir plusieurs solutions
Laquelle est la plus efficace ?
Solution A
1 000 000 opérations
Pour 1000 éléments
Solution B
1 000 opérations
Pour 1000 éléments
La solution B est 1000x plus rapide!
Big O = Estimation du comportement
Pas un comptage exact, mais une tendance
O(1)
Temps constant
Toujours la mĂŞme vitesse
O(n)
Temps linéaire
Proportionnel Ă N
O(n²)
Temps quadratique
Explose rapidement
On ignore les constantes : O(2n) = O(n)
Toujours la mĂŞme vitesse, peu importe N
Accès par index dans un tableau
const tableau = [10, 20, 30, 40, 50];
const premier = tableau[0]; // O(1)
const troisieme = tableau[2]; // O(1)
const dernier = tableau[4]; // O(1)
1 seule opération, quelle que soit la taille
5 éléments
1 op
100 éléments
1 op
1 000 000 éléments
1 op
Proportionnel au nombre d'éléments
Doubler N = Doubler le temps
function trouverMax(tableau) {
let max = tableau[0];
for (let i = 0; i < tableau.length; i++) {
if (tableau[i] > max) {
max = tableau[i];
}
}
return max;
}
La boucle parcourt tous les éléments
10 éléments
10 ops
100 éléments
100 ops
1000 éléments
1000 ops
Deux boucles imbriquées
Ça explose vite avec de grands tableaux
function comparerTous(tableau) {
for (let i = 0; i < tableau.length; i++) {
for (let j = 0; j < tableau.length; j++) {
console.log(tableau[i], tableau[j]);
}
}
}
Pour chaque élément, on reparcourt tout le tableau!
10 éléments
100 ops
100 éléments
10 000 ops
1000 éléments
1 000 000 ops
| N éléments | O(1) | O(n) | O(n²) |
|---|---|---|---|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10 000 |
| 1 000 | 1 | 1 000 | 1 000 000 |
| 10 000 | 1 | 10 000 | 100 000 000 |
O(n²) avec 10 000 éléments = 100 millions d'opérations!
O(1) = Plat
Toujours rapide
O(n) = Pente douce
Croissance raisonnable
O(n²) = Explosion
Signal d'alarme!
Compter les opérations
Identifions ensemble la complexité!
function premierElement(tableau) {
return tableau[0];
}
Combien d'opérations pour un tableau de :
10 éléments
?
100 éléments
?
1000 éléments
?
RĂ©ponse : O(1)
1 seule opération : accès direct à l'index 0
function somme(tableau) {
let total = 0;
for (let i = 0; i < tableau.length; i++) {
total += tableau[i];
}
return total;
}
RĂ©ponse : O(n)
La boucle parcourt chaque élément une fois
N éléments = N opérations
function doublons(tableau) {
for (let i = 0; i < tableau.length; i++) {
for (let j = i + 1; j < tableau.length; j++) {
if (tableau[i] === tableau[j]) {
return true;
}
}
}
return false;
}
Réponse : O(n²)
Deux boucles imbriquées = n × n opérations
Pour 100 éléments : ~5000 comparaisons
Big O trop abstrait?
Utilisez des exemples concrets avec des nombres réels
"Pour 1000 éléments, O(n) = 1000 ops, O(n²) = 1 000 000 ops"
Éviter la notation formelle
Rester sur l'intuition : "ça double" vs "ça explose"
Pas besoin de limites mathématiques!
Différencier "rapide" et "lent"
O(1) = instantané (accès direct)
O(n) = proportionnel (parcours)
O(n²) = signal d'alarme (à éviter si possible)
L'erreur
// O(n²) pour chercher
for (let i of tableau) {
for (let j of tableau) {
if (i === cible && j === cible) {
return true;
}
}
}
Inutilement complexe!
La solution
// O(n) pour chercher
for (let element of tableau) {
if (element === cible) {
return true;
}
}
Simple et efficace!
Une seule boucle suffit pour chercher un élément
Algorithme = suite d'étapes pour résoudre un problème
Big O = estimation, pas comptage exact
On s'intéresse à la tendance, pas aux constantes
O(n) = proportionnel au nombre d'éléments
Doubler N = doubler le temps
O(n²) = signal d'alarme!
Ça explose vite avec de grands tableaux
Pseudo-code
DĂ©crire avant de coder
Planifier la logique
Complexité
Mesurer l'efficacité
Comparer les solutions
O(1) / O(n)
Constant / Linéaire
Acceptable
O(n²)
Quadratique
Attention!
Écrivez toujours du pseudo-code avant de coder
Identifiez les boucles pour trouver la complexité
O(n²) = demander s'il existe une meilleure solution
Pratiquez avec des exemples concrets et des nombres
La complexité, c'est penser à l'efficacité
Prochaine étape : Mesurer le temps réel en JavaScript