0Pricing
DSA Interview Prep · Leçon

Analyser les boucles et les boucles imbriquées

Calculez la complexité temporelle des boucles simples, des boucles imbriquées et des boucles dont les intervalles se réduisent, comme dans la recherche binaire ou les itérations triangulaires.

Analyser les boucles et les boucles imbriquées est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 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 DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.

Boucle simple : O(n)

La boucle la plus simple exécute son corps n fois, donc elle est en O(n). Un pas plus grand modifie le nombre d’exécutions, mais pas la classe. Commencez toujours par compter combien de fois le corps s’exécute. Consultez le code.

# O(n): body runs n times
def count_ops_linear(n):
    ops = 0
    for i in range(n):
        ops += 1     # constant work
    return ops

print(count_ops_linear(100))  # 100

# Still O(n): step=2 halves count but same class
def count_ops_half(n):
    ops = 0
    for i in range(0, n, 2):
        ops += 1
    return ops

print(count_ops_half(100))    # 50  => O(n)

Boucles imbriquées : O(n²) et au-delà

Deux boucles imbriquées qui s’exécutent chacune n fois donnent n × n = O(n^2) ; trois boucles donnent O(n^3). Mais si la boucle interne s’exécute un nombre fixe de fois, l’ensemble reste linéaire.

def count_pairs(n):
    ops = 0
    for i in range(n):          # n iterations
        for j in range(n):      # n iterations each
            ops += 1
    return ops

print(count_pairs(10))   # 100 = 10^2
print(count_pairs(100))  # 10000 = 100^2
# Doubling n quadruples ops: classic O(n^2)

Boucle triangulaire : O(n²/2) = O(n²)

Lorsque la boucle interne commence à i+1, les itérations forment un triangle : n(n-1)/2, ce qui reste O(n^2) après suppression du facteur deux. Les problèmes portant sur toutes les paires uniques ont cette forme.

def count_unique_pairs(n):
    ops = 0
    for i in range(n):          # n iterations
        for j in range(i+1, n): # n-1, n-2, ..., 0
            ops += 1
    return ops

print(count_unique_pairs(10))  # 45 = 10*9/2
print(count_unique_pairs(100)) # 4950
# Still O(n^2) -- constant factor 1/2 dropped

Boucle à plage décroissante : O(log n)

Lorsque la variable de boucle est divisée par deux à chaque étape, on obtient O(log n). La question essentielle est la suivante : la plage diminue-t-elle de manière multiplicative (log n) ou additive (n) ? Consultez le code.

def count_log_ops(n):
    ops = 0
    i = n
    while i >= 1:
        ops += 1
        i //= 2   # halve each iteration
    return ops

import math
for n in [8, 16, 64, 1024]:
    ops = count_log_ops(n)
    print(f'n={n}, ops={ops}, log2={int(math.log2(n))}')
# ops tracks log2(n) closely

Boucle imbriquée avec boucle interne décroissante : O(n log n)

Une boucle externe exécutée n fois avec une boucle interne en O(log n) donne O(n log n) — c’est la structure du tri fusion. Repérer une étape interne en O(log n) est essentiel pour analyser les algorithmes de tri.

import math

def count_n_log_n(n):
    ops = 0
    for i in range(n):    # n iterations
        j = n
        while j >= 1:     # log n iterations
            ops += 1
            j //= 2
    return ops

for n in [8, 32, 128]:
    ops = count_n_log_n(n)
    predicted = int(n * math.log2(n))
    print(f'n={n}: actual={ops}, n*log2(n)~={predicted}')

Boucles internes dépendantes

Lorsque la plage de la boucle interne dépend de l’indice externe, comptez le nombre total d’itérations, et non celui de chaque étape. Une boucle interne allant de 0 à i donne une somme égale à n(n-1)/2 = O(n^2). Consultez le code.

# Inner loop runs i times: total = 0+1+2+...+(n-1) = n(n-1)/2 => O(n^2)
def sum_inner_i(n):
    ops = 0
    for i in range(n):
        for j in range(i):   # runs 0,1,2,...,n-1 times
            ops += 1
    return ops

print(sum_inner_i(10))  # 45 = 10*9/2  => O(n^2)

# Inner loop runs n/i times (i doubles): sum ≈ n*log n => O(n log n)
def sum_inner_n_over_i(n):
    ops = 0
    i = 1
    while i <= n:
        for j in range(n // i):
            ops += 1
        i *= 2
    return ops
print(sum_inner_n_over_i(64))  # ~ 64*6 = 384

Analyse du tri à bulles, étape par étape

Le tri à bulles effectue n(n-1)/2 comparaisons, donc il est en O(n^2). Même avec un arrêt anticipé, une entrée triée dans l’ordre inverse nécessite toutes les comparaisons. Il est trop lent pour les grandes entrées.

def bubble_sort(arr):
    n = len(arr)
    comparisons = 0
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            comparisons += 1
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:  # early exit if sorted
            break
    return comparisons

arr = list(range(10, 0, -1))  # worst case: reversed
ops = bubble_sort(arr)
print(f'Sorted: {arr}')
print(f'Comparisons: {ops}')  # 45 = 10*9/2

Boucles sur les chaînes et les sous-chaînes

Attention : le découpage en tranches de Python est en O(k), il n’est pas gratuit, et la concaténation de chaînes avec + dans une boucle est en O(n^2), car chaque chaîne est copiée à chaque fois. Utilisez plutôt ''.join(parts). Consultez le code.

# O(n^2): string concat in loop
def build_bad(n):
    s = ''
    for i in range(n):
        s += str(i)  # copies s each time!
    return s

# O(n): join is a single pass
def build_good(n):
    parts = []
    for i in range(n):
        parts.append(str(i))
    return ''.join(parts)

print(build_good(10))  # '0123456789'

Paramètres d’entrée multiples

Avec deux entrées, la complexité peut utiliser les deux paramètres : O(m + n) pour des traitements séparés, O(m × n) pour des traitements imbriqués. Les graphes s’expriment souvent en O(V + E). Nommez clairement chaque variable.

# O(m + n): two independent loops
def independent(m, n):
    a = sum(range(m))  # O(m)
    b = sum(range(n))  # O(n)
    return a + b       # total O(m + n)

# O(m * n): nested
def nested(m, n):
    count = 0
    for i in range(m):     # O(m)
        for j in range(n): # O(n) each
            count += 1
    return count  # O(m * n)

print(independent(5, 10))  # 10 + 45 = 55
print(nested(5, 10))       # 50

Boucle dans une boucle ou appels séquentiels

Un appel de fonction n’est pas gratuit : sa boucle interne doit également être comptée. Appeler n fois un utilitaire en O(n) donne O(n^2). Examinez toujours l’intérieur des appels opaques lors de l’analyse.

# Naive string matching: O(n*m)
def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    matches = []
    for i in range(n - m + 1):  # O(n)
        if text[i:i+m] == pattern:  # O(m) comparison + O(m) slice
            matches.append(i)
    return matches
# Total: O(n*m)

print(naive_search('abcabcabc', 'abc'))  # [0, 3, 6]

En pratique : identifier la complexité d’un coup d’œil

Prenez une bonne habitude : comptez les niveaux d’imbrication des boucles, vérifiez si la boucle interne dépend de la boucle externe et recherchez les coûts cachés dans les appels de fonctions et le découpage en tranches. Le code vous propose un exercice à essayer.

# What is the complexity of this function?
def mystery(nums):
    result = []
    for i in range(len(nums)):          # O(n)
        for j in range(i, len(nums)):   # O(n) worst
            if sum(nums[i:j+1]) == 0:   # O(n) slice + sum!
                result.append((i, j))
    return result
# Answer: O(n^3)  -- three nested n-proportional ops
# Outer O(n) x inner O(n) x sum/slice O(n) = O(n^3)

Vérification rapide

Vérification rapide — voyons si les techniques d’analyse des boucles sont bien restées. Faites confiance à votre raisonnement. 💪

Récapitulatif de la leçon

Récapitulatif : les boucles imbriquées se multiplient et les boucles indépendantes s’additionnent ; une boucle interne qui réduit de moitié donne O(n log n), et les coûts cachés dans les appels et le découpage en tranches doivent également être comptés.

Questions Fréquemment Posées

La leçon « Analyser les boucles et les boucles imbriquées » est-elle gratuite ?

Oui — le texte complet de « Analyser les boucles et les boucles imbriquées » 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 DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Analyser les boucles et les boucles imbriquées » ?

Calculez la complexité temporelle des boucles simples, des boucles imbriquées et des boucles dont les intervalles se réduisent, comme dans la recherche binaire ou les itérations triangulaires. Tu pratiques DSA 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 DSA Interview Prep ?

Aucune expérience préalable n'est requise. DSA 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 2 sur 4.

Combien de temps prend la leçon « Analyser les boucles et les boucles imbriquées » ?

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 DSA Interview Prep ?

Oui. Chaque leçon DSA 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

  1. La notation grand O depuis le début
  2. Analyser les boucles et les boucles imbriquées
  3. Récursivité et méthode de l’arbre de récursion
  4. Complexité spatiale et compromis
← Retour à DSA Interview Prep