8. Analyse du Temps Quadratique : O(N²)

Un algorithme s'exécute en Temps Quadratique, O(N²), si le temps d'exécution augmente proportionnellement au carré de la taille de l'entrée (N).

Si l'entrée double (N devient 2N), le temps d'exécution quadruple (N² devient 4N²).

Exemple : Boucles Imbriquées

L'exemple classique de O(N²) est d'avoir deux boucles imbriquées, où la boucle intérieure itère complètement pour chaque itération de la boucle extérieure.

python def print_all_pairs(data): N = len(data) # Outer loop runs N times (O(N)) for i in range(N): # Inner loop runs N times for each outer iteration (O(N)) for j in range(N): print(data[i], data[j]) # Total operations = N * N = N²

Les algorithmes avec une complexité O(N²) (comme le Bubble Sort, que nous verrons plus tard) sont généralement considérés comme lents et inefficaces pour les grands ensembles de données.