Compter les opérations avec Big-O
Du constant au quadratique, en termes simples
Compter les opérations avec Big-O est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Pourquoi compter les opérations
Dans les concours, la rapidité est décisive. Au lieu de chronométrer votre code, vous estimez le nombre d'étapes nécessaires. Cette estimation est sa complexité temporelle. 🚀
Découvrir Big-O
Big-O décrit la croissance du nombre d'opérations lorsque la taille d'entrée n augmente. Il ignore les petits détails et se concentre sur la tendance dominante.
Temps constant O(1)
Lorsque le travail ne dépend jamais de n, il est en O(1). Lire un élément d'une liste ou effectuer une addition prend toujours le même temps.
x = arr[0]
y = a + bTemps linéaire O(n)
Une simple boucle parcourant n éléments est en O(n). Si vous doublez la taille de l'entrée, vous doublez approximativement le travail. C'est l'outil de base du quotidien.
for x in arr:
total += xTemps quadratique O(n au carré)
Une boucle à l'intérieur d'une autre, toutes deux parcourant n éléments, est en O(n^2). Pour n = 1000, cela représente un million d'étapes, et la croissance s'accélère rapidement ensuite.
for i in range(n):
for j in range(n):
check(i, j)Temps logarithmique O(log n)
Lorsque chaque étape divise le problème par deux, vous obtenez O(log n). Une recherche binaire atteint un milliard d'éléments en seulement une trentaine d'étapes. ✨
L'échelle de croissance
Du plus rapide au plus lent, l'ordre courant est le suivant : O(1), O(log n), O(n), O(n log n), O(n^2). Plus vous êtes haut dans cette liste, meilleure est la mise à l'échelle.
Supprimer les constantes
Big-O ignore les facteurs constants : O(2n) devient donc simplement O(n). Deux parcours restent linéaires, le multiplicateur ne change donc pas la classe.
Ne garder que le terme dominant
Lorsque les termes s'additionnent, seul celui qui croît le plus rapidement compte. O(n^2 + n) se simplifie en O(n^2), car n^2 devient très supérieur à n lorsque n augmente.
Séquentielles ou imbriquées
Deux boucles exécutées l'une après l'autre s'additionnent : O(n + n) = O(n). Deux boucles imbriquées se multiplient et donnent O(n^2). La structure des boucles vous indique laquelle s'applique.
Commencer par le pire cas
Les concours évaluent le cas le plus difficile, vous devez donc raisonner sur le pire cas. Supposez que la boucle s'exécute entièrement, et non qu'elle s'arrête prématurément.
Vérification rapide
Il est temps d'évaluer votre intuition de Big-O.
Récapitulatif
Vous savez maintenant lire la croissance dans le code : O(1), O(n), O(n^2) et O(log n). Supprimez les constantes, gardez le terme dominant et pensez au pire cas. 🎯
Questions Fréquemment Posées
La leçon « Compter les opérations avec Big-O » est-elle gratuite ?
Oui — le texte complet de « Compter les opérations avec Big-O » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Compter les opérations avec Big-O » ?
Du constant au quadratique, en termes simples Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Compter les opérations avec Big-O » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Compter les opérations avec Big-O
- La règle empirique des 10^8
- Lire les contraintes et choisir la complexité
- Pourquoi TLE survient et comment le repérer