Complexité algorithmique
\( T(n) = O(f(n)) \)
Notation de Landau
Exemple O(1) :
Accès direct à un tableau :
tableau[i]
Exemple O(n) :
Recherche linéaire dans un tableau non trié
Types de complexité
Temps d'exécution
Espace mémoire
Dépendance de n
Pire cas / Cas moyen
Notations asymptotiques
O(g(n)): borne supérieure
Ω(g(n)): borne inférieure
Θ(g(n)): borne exacte
Classes de complexité
| Classe | Complexité | Exemple |
|---|---|---|
| Constante | O(1) | Accès tableau |
| Logarithmique | O(log n) | Recherche dichotomique |
| Linéaire | O(n) | Recherche linéaire |
| Quadratique | O(n²) | Bulle/tri sélection |
| Exponentielle | O(2ⁿ) | Problèmes combinatoires |
Méthodes de mesure
Analyse théorique :
Étude du nombre d'opérations élémentaires
Tests expérimentaux :
Chronométrage avec des jeux de données variés
Algorithmes et exemples détaillés
Tri par sélection - O(n²)
def tri_selection(tab):
n = len(tab)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if tab[j] < tab[min_idx]:
min_idx = j
tab[i], tab[min_idx] = tab[min_idx], tab[i]
return tabBoucles imbriquées → O(n²)
Recherche dichotomique - O(log n)
def recherche_dicho(tab, x):
debut, fin = 0, len(tab)-1
while debut <= fin:
milieu = (debut + fin) // 2
if tab[milieu] == x:
return milieu
elif tab[milieu] < x:
debut = milieu + 1
else:
fin = milieu - 1
return -1Divise par 2 à chaque étape → O(log n)
Conseils pour optimisation
Éviter les boucles imbriquées si possible
Privilégier les structures adaptées (dict, set)
Tester avec des tailles différentes
Optimiser la complexité spatiale aussi
