Algorithmes et complexité
Si ton algo met 10 ans à trier 100 nombres, t'as un problème. Pas de coupe de cheveux, mais un problème de complexité.
Cours
Complexité
La complexité mesure le nombre d'opérations en fonction de la taille des données $n$.
Notation O (grand O) : on ignore les constantes et les termes de plus bas degré.
| Algo | Complexité |
|---|---|
| Recherche dichotomique | O(log n) |
| Tri par insertion | O(n²) |
| Tri fusion / rapide (moy.) | O(n log n) |
| Recherche linéaire | O(n) |
Recherche dichotomique
def dicho(L, x):
g, d = 0, len(L) - 1
while g <= d:
m = (g + d) // 2
if L[m] == x:
return m
elif L[m] < x:
g = m + 1
else:
d = m - 1
return -1
→ Tableau trié obligatoire. Diviser par 2 à chaque étape → O(log n).
Tri par insertion
def tri_insertion(L):
for i in range(1, len(L)):
x = L[i]
j = i - 1
while j >= 0 and L[j] > x:
L[j+1] = L[j]
j -= 1
L[j+1] = x
return L
→ O(n²). Simple mais lent sur grand tableau.
Récursivité
Une fonction qui s'appelle elle-même. Doit avoir un cas de base sinon stack overflow.
def factorielle(n):
if n <= 1:
return 1
return n * factorielle(n - 1)
Formules clés
Méthodes
Évaluer la complexité d'une boucle
- 1Compter le nombre d'itérations en fonction de n
- 2Boucle for i in range(n) : n itérations → O(n)
- 3Deux boucles imbriquées sur n : n² itérations → O(n²)
- 4Diviser par 2 à chaque étape : log n itérations → O(log n)
Astuces & pièges
Pour log₂(n) : n=1024 donne 10. n=1 million donne ~20. Tu vois la magie ? La dichotomie écrase la recherche linéaire.
Dichotomie = tableau TRIÉ. Sinon ça ne marche tout simplement pas.
Récursivité : TOUJOURS un cas de base. Sinon RecursionError. Python limite à ~1000 appels par défaut.
L'algo "bogosort" trie en mélangeant aléatoirement jusqu'à tomber sur le bon ordre. Complexité moyenne : O(n!). On évite.
Teste-toi
1.Complexité de la recherche dichotomique :
2.Tri par insertion sur tableau de 1000 éléments ≈
3.Une fonction récursive sans cas de base :