J'ai echoue a mon premier entretien technique sur les algorithmes parce que j'ai repondu "ca depend" quand on m'a demande la complexite temporelle d'une fonction de recherche. L'examinateur attendait O(log n). Je savais que c'etait une recherche binaire. Je savais meme que c'etait logarithmique. Mais j'ai panique et je me suis mis a divaguer sur les lignes de cache, la prediction de branchement et la question de savoir si le tableau tenait dans le L1. Les yeux de l'examinateur se sont vitrifies. "Ca depend" est techniquement correct, mais pratiquement inutile quand quelqu'un veut savoir si votre solution fonctionnera encore lorsque l'entree passera de 1 000 a 1 000 000.
Cet entretien m'a appris quelque chose qu'il m'a fallu des annees pour interioriser pleinement : la notation Big O ne vise pas la precision. Elle decrit la forme de la croissance. Elle vous dit comment un algorithme se comporte lorsque l'entree augmente ; pas le nombre exact d'operations, pas le temps reel d'execution, mais la courbe.
Et une fois que vous voyez les courbes, tout devient limpide.
Pourquoi Big O compte au-dela des entretiens
Soyons directs : la plupart des developpeurs en poste que je connais ont appris Big O pour les entretiens et l'ont aussitot oublie. C'est une erreur.
L'annee derniere, j'avais un service en production qui fonctionnait parfaitement avec 500 utilisateurs et s'effondrait a 5 000. Le coupable etait une boucle imbriquee que personne n'avait remarquee lors de la revue de code. Deux appels .filter() a l'interieur d'un .map(). Le code avait l'air propre. Se lisait agreablement. Et sa complexite etait O(n^3). Avec 500 elements, l'execution prenait 120 ms. Avec 5 000 elements ; 12 secondes. Avec 50 000 elements, cela aurait pris 20 minutes.
La complexite temporelle fait la difference entre "ca marche sur ma machine" et "ca marche en production". C'est la raison pour laquelle certains systemes montent en charge avec elegance tandis que d'autres heurtent un mur. Ce n'est pas academique. C'est la chose la plus pratique en informatique.
Les huit classes de complexite ; du vrai code, de vraies consequences
Passons en revue chaque classe avec du code reel que vous pouvez executer. J'utilise JavaScript parce que la plupart des developpeurs le lisent comme du pseudocode, mais les concepts sont independants du langage.
O(1) ; temps constant
function getFirst(arr) {
return arr[0];
}
Peu importe que le tableau contienne 10 elements ou 10 millions. Une seule operation. Les recherches dans les tables de hachage sont aussi O(1) en moyenne ; c'est pourquoi vous utilisez un Map ou un objet quand vous avez besoin d'un acces rapide par cle. Le "en moyenne" a son importance (les collisions de hachage existent), mais en pratique c'est la reference absolue.
O(log n) ; logarithmique
function binarySearch(sorted, target) {
let lo = 0, hi = sorted.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (sorted[mid] === target) return mid;
if (sorted[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
La recherche binaire divise le probleme par deux a chaque etape. Chercher parmi 1 milliard d'elements tries ? Environ 30 comparaisons. C'est la magie des logarithmes. Chaque fois que vous doublez l'entree, vous n'ajoutez qu'une seule etape supplementaire. Les index de bases de donnees fonctionnent sur ce principe (les B-trees sont essentiellement une recherche binaire multidirectionnelle).
O(n) ; lineaire
function findMax(arr) {
let max = arr[0];
for (const val of arr) {
if (val > max) max = val;
}
return max;
}
On parcourt chaque element une fois. Doublez l'entree, doublez le temps. C'est souvent le mieux que vous puissiez faire quand vous devez examiner toutes les donnees. Si quelqu'un vous demande d'"optimiser" un parcours lineaire qui a reellement besoin de voir chaque element, il vous demande un miracle.
O(n log n) ; linearithmique
C'est la ou vivent les tris par comparaison efficaces. Merge sort, quicksort (cas moyen), heapsort. Il existe une borne inferieure prouvee ici ; il est impossible de trier n elements en comparant des paires en moins de O(n log n) comparaisons. C'est une impossibilite mathematique, demontree via les arbres de decision.
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(a, b) {
const result = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
result.push(a[i] <= b[j] ? a[i++] : b[j++]);
}
return result.concat(a.slice(i), b.slice(j));
}
La complexite temporelle de merge sort est O(n log n) dans tous les cas ; pire, moyen et meilleur. C'est pourquoi il est le tri par defaut dans de nombreuses bibliotheques standard. Sa complexite spatiale est cependant O(n) ; il faut ce tableau auxiliaire. Des compromis partout.
O(n^2) ; quadratique
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
Deux boucles imbriquees sur l'entree. 1 000 elements signifient environ 1 000 000 d'operations. 10 000 elements signifient environ 100 000 000. C'est la que vivent les bugs du type "ca marche bien en developpement". Le .filter() imbrique dans un .map() que j'ai mentionne plus tot ? Le piege quadratique classique deguise en syntaxe fonctionnelle.
O(2^n) ; exponentiel
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
La suite de Fibonacci recursive naive. Chaque appel se divise en deux appels supplementaires. A n=30, vous effectuez plus d'un milliard d'appels de fonctions. A n=50, votre machine capitule. La solution est la memoisation (qui ramene la complexite a O(n)) ou une approche iterative. Mais la version naive est l'exemple canonique illustrant pourquoi les algorithmes exponentiels sont en pratique inutilisables pour tout ce qui depasse de petites entrees.
O(n!) ; factoriel
function permutations(arr) {
if (arr.length <= 1) return [arr];
const result = [];
for (let i = 0; i < arr.length; i++) {
const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
for (const perm of permutations(rest)) {
result.push([arr[i], ...perm]);
}
}
return result;
}
La generation de toutes les permutations. 10 elements = 3 628 800 permutations. 15 elements = plus de 1 300 milliards. 20 elements = plus que le nombre de secondes depuis le debut de l'univers. Le probleme du voyageur de commerce vit ici (force brute). C'est pourquoi les problemes NP-difficiles sont difficiles ; si vous trouvez une solution efficace a l'un d'entre eux, allez chercher votre prix du millenaire.
Voir les courbes rend les choses concretes
J'ai construit un Comparateur de complexite Big O parce que fixer une notation sur une page ne transmet pas la difference viscerale entre ces classes. Quand vous tracez O(n), O(n log n) et O(n^2) sur le meme graphique, la courbe quadratique monte si agressivement que la lineaire semble plate en comparaison. Et O(2^n) et O(n!) font paraitre O(n^2) plat.
L'outil trace les huit classes simultanement sur une echelle logarithmique afin que vous puissiez voir les relations. Jouez avec le curseur de taille d'entree et observez ce qui se passe au-dessus de n=20. Les courbes exponentielle et factorielle sortent completement du graphique. Ce n'est pas une exageration pour l'effet visuel ; ce sont les valeurs reelles. A n=25, O(n!) vaut 15 511 210 043 330 985 984 000 000. Votre solution O(n^2) a soudainement l'air rapide en comparaison.
Trois erreurs courantes a propos de Big O
1. Les constantes comptent en pratique. Big O elimine les constantes. O(2n) et O(n) sont tous deux "O(n)". Mais dans du code reel, un facteur constant de 10x fait la difference entre une reponse de 100 ms et une reponse d'une seconde. Un algorithme avec une boucle interne serree et une bonne localite de cache en O(n log n) ecrasera un algorithme theoriquement equivalent en O(n log n) qui malmene la memoire. CLRS (la bible des algorithmes ; Introduction to Algorithms de Cormen, Leiserson, Rivest et Stein) le reconnait ; les "facteurs constants" qu'il evacue dans les preuves deviennent des decisions d'ingenierie en production.
2. La complexite amortie n'est pas la complexite moyenne. Quand on dit que ArrayList.add() est O(1) amorti, cela signifie que parfois c'est O(n) (quand il faut redimensionner), mais que ces operations couteuses sont reparties de sorte que sur n operations, le cout total est O(n). C'est different de dire que le cas moyen est O(1). L'amortissement est une garantie sur une sequence ; le cas moyen depend de la distribution des entrees.
3. La complexite spatiale est tout aussi importante. J'ai vu des ingenieurs optimiser la complexite temporelle de O(n^2) a O(n) et celebrer ; pour decouvrir ensuite que leur solution O(n) utilisait O(n^2) en espace. Sur un serveur avec 4 Go de RAM traitant 10 millions d'enregistrements, la complexite spatiale vous acheve plus vite que la complexite temporelle. Posez toujours les deux questions : combien de temps cela prend-il, et combien de memoire cela necessite-t-il ?
Comment analyser votre propre code
Voici ma methode etape par etape. Je l'applique a chaque fois que je relis du code qui traite des entrees de taille variable :
- Identifiez l'entree. Quelle variable determine la taille ? En general, c'est la longueur d'un tableau, le nombre de lignes, le nombre de noeuds.
- Reperer les boucles. Chaque boucle qui itere sur l'entree contribue au minimum a O(n). Les boucles imbriquees multiplient.
- Attention aux boucles cachees. Les methodes de tableaux comme
.filter(),.map(),.indexOf(),.includes()sont toutes O(n). En chainer trois reste O(n) ; en imbriquer une dans une autre donne O(n^2). - Verifiez les appels recursifs. Combien de fois la fonction s'appelle-t-elle elle-meme ? Une recursion binaire (deux appels) est O(2^n) sans memoisation. Si la recursion divise le probleme par deux a chaque fois, c'est O(log n).
- Tenez compte des operations natives.
Array.sort()est O(n log n).Set.has()est O(1).Array.includes()est O(n). Connaissez votre bibliotheque standard.
Preparation aux entretiens ; cinq schemas qui couvrent 80 % des questions
Apres avoir passe environ 200 entretiens de programmation (des deux cotes de la table), voici mon aide-memoire Big O pour les schemas qui reviennent constamment :
1. Table de hachage pour eliminer une boucle imbriquee. Si votre approche brute force est O(n^2) parce que vous cherchez un complement ou une correspondance dans une boucle interne, une table de hachage la rend O(n). Exemple classique : two sum.
2. Trier d'abord, puis utiliser une recherche binaire ou deux pointeurs. Le tri coute O(n log n) en amont mais deverrouille des recherches en O(log n). Total : O(n log n). Presque toujours meilleur que la force brute en O(n^2).
3. Fenetre glissante pour les problemes de sous-tableau ou sous-chaine. Transforme une force brute O(n^2) ou O(n^3) en O(n) en maintenant une fenetre qui avance dans les donnees. Sous-tableau maximal, plus longue sous-chaine sans repetition ; tout cela releve de la fenetre glissante.
4. Diviser pour regner pour O(n log n). Divisez le probleme, resolvez les moities recursivement, combinez. Merge sort est l'exemple du manuel, mais ce schema apparait dans la paire de points la plus proche, le comptage d'inversions et la multiplication matricielle.
5. Programmation dynamique pour eliminer la recursion exponentielle. Memoisez les sous-problemes chevauchants pour faire passer O(2^n) a O(n) ou O(n^2). Fibonacci, rendu de monnaie, plus longue sous-sequence commune. Si vous reperer des sous-problemes chevauchants et une sous-structure optimale, pensez a la programmation dynamique.
Ces cinq schemas ne couvrent pas tout, mais ils couvrent suffisamment pour reussir la plupart des entretiens algorithmiques. Pour aller plus loin, je recommande sincerement de travailler les problemes avec un comparateur visuel de complexite ouvert. Voir ou votre solution se situe sur la courbe construit l'intuition plus vite que la memorisation de regles.
Explorez d'autres outils
Si vous avez trouve le Comparateur de complexite Big O utile, decouvrez le reste de la collection Visualiseurs et Logique sur Kitmul. Nous proposons des outils de visualisation de regex, d'exploration d'AST et d'autres fondamentaux de l'informatique. Tous gratuits, tous dans le navigateur, tous prives ; vos donnees ne quittent jamais votre machine.
Confidentialite : Chaque outil sur Kitmul fonctionne entierement dans votre navigateur. Aucune donnee n'est envoyee a un serveur. Aucun compte requis. Aucun suivi au-dela des statistiques de base.