Algorithme
Analyser avec la notation grand O comment le temps et la mémoire d'un algorithme croissent avec la taille de l'entrée, puis le vérifier par la mesure.
L'analyse de complexité décrit comment le temps et la mémoire nécessaires à un algorithme augmentent quand son entrée grandit. Plutôt que des secondes, qui dépendent du matériel et du langage, elle compte les opérations élémentaires en fonction de la taille n de l'entrée et ne garde que le terme dominant. Le résultat s'écrit en notation asymptotique : grand O pour une borne supérieure, grand Oméga pour une borne inférieure et grand Thêta pour une borne exacte.
Elle compte parce que, lorsque les données augmentent, l'écart entre les ordres de croissance dépasse n'importe quel facteur constant. Une routine en O(n²) qui convient pour mille éléments peut prendre des heures sur un million, alors qu'une version en O(n log n) se termine en quelques secondes. La complexité sert à choisir les structures de données, à lire les contraintes d'entrée d'un exercice de programmation, à repérer des coûts cachés en revue de code et à estimer si un système passera à l'échelle.
Commencez par compter les opérations de boucles simples et par apprendre les classes courantes : O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) et O(n!). Passez ensuite aux cas favorable, moyen et défavorable, à l'analyse amortie, à la complexité spatiale et à la résolution de récurrences avec le théorème maître. Vérifiez toujours votre raisonnement par une expérience de doublement : mesurez le code pour n et 2n, puis comparez le rapport.
O, Ω et Θ donnent des bornes supérieures, inférieures et exactes de la croissance, en ignorant les constantes et les termes d'ordre inférieur.
Les blocs successifs additionnent leurs coûts, les boucles imbriquées les multiplient, et diviser le problème par deux à chaque étape fait apparaître un logarithme.
Elle répartit le coût sur toute une suite d'opérations ; c'est pourquoi l'ajout dans un tableau dynamique est en O(1) même s'il faut parfois tout recopier.
La mémoire auxiliaire et la profondeur de récursion comptent aussi, et le théorème maître résout les récurrences de type diviser pour régner.
Le script résout le même problème de deux façons : en testant toutes les paires, ou en un seul passage qui mémorise les valeurs déjà vues dans un dictionnaire. En mesurant les deux avec timeit pour n = 500, 1 000 et 2 000, chaque doublement rend la version quadratique environ quatre fois plus lente et la version linéaire environ deux fois plus lente.
complexity.py
import timeit
def two_sum_quadratic(nums, target):
"""O(n^2): try every pair."""
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
return None
def two_sum_linear(nums, target):
"""O(n) on average: remember values already seen."""
seen = {}
for j, x in enumerate(nums):
i = seen.get(target - x)
if i is not None:
return i, j
seen.setdefault(x, j)
return None
print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))
for n in (500, 1_000, 2_000):
nums = list(range(0, 2 * n, 2)) # even numbers only, so no pair sums to -1
slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
print(f"n={n:>5} O(n^2) {slow * 1000:8.2f} ms O(n) {fast * 1000:6.3f} ms")
python complexity.pySix chapitres pour aller de l'installation aux notions essentielles de Analyse de complexité.
Posez vos questions, partagez votre expérience et échangez vos avis sur Analyse de complexité.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.