est une branche fondamentale de l'informatique qui s'intéresse à l'efficacité des algorithmes en termes de ressources qu'ils consomment, notamment le temps et l'espace mémoire. Voici un résumé détaillé de la complexité algorithmique, accompagné d'exemples et d'exercices résolus.
### 1. Concepts de base
- **Complexité temporelle :** Mesure le temps qu'un algorithme met pour exécuter sa tâche en fonction de la taille de l'entrée. On utilise souvent la notation Big O (O(n), O(log n), O(n²), etc.).
- **Complexité spatiale :** Mesure la mémoire utilisée par l'algorithme en fonction de la taille de l'entrée.
### 2. Notations de complexité
- **O(1) :** Complexité constante. Le temps d'exécution ne dépend pas de la taille de l'entrée.
- **Exemple :** Accéder à un élément d'un tableau par son index.
- **O(log n) :** Complexité logarithmique. Typiquement observée dans les algorithmes de recherche binaire.
- **Exemple :** Recherche d'un élément dans une liste triée.
- **O(n) :** Complexité linéaire. Le temps d'exécution augmente proportionnellement à la taille de l'entrée.
- **Exemple :** Parcourir tous les éléments d'un tableau.
- **O(n log n) :** Complexité linéaireithmique. Souvent trouvée dans des algorithmes de tri efficaces comme le tri rapide (Quicksort).
- **O(n²) :** Complexité quadratique. Fréquent dans les algorithmes de tri simples, tels que le tri par bulle.
- **O(2^n) :** Complexité exponentielle. Typique des algorithmes de force brute, comme le problème du voyageur de commerce pour de grandes entrées.
### 3. Exemples
#### Exercice 1 : Trouver la somme des éléments d'un tableau
```python
def somme(tab):
total = 0
for element in tab:
total += element
return total
```
- **Complexité temporelle :** O(n) parce qu'on parcourt chaque élément une fois.
#### Exercice 2 : Vérifier si un élément existe dans un tableau non trié
```python
def existe(tab, element):
for el in tab:
if el == element:
return True
return False
```
- **Complexité temporelle :** O(n) car dans le pire des cas, on doit vérifier chaque élément.
### 4. Exercices Résolus
#### Exercice 3 : Recherche binaire
1. Écrire une fonction qui effectue une recherche binaire sur un tableau trié.
```python
def recherche_binaire(tab, element):
gauche = 0
droite = len(tab) - 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if tab[milieu] == element:
return milieu
elif tab[milieu] < element:
gauche = milieu + 1
else:
droite = milieu - 1
return -1
```
- **Complexité temporelle :** O(log n)
#### Exercice 4 : Tri par bulle
Écrire une fonction pour trier un tableau par le algorithme de tri par bulle.
```python
def tri_bulle(tab):
n = len(tab)
for i in range(n):
for j in range(0, n-i-1):
if tab[j] > tab[j+1]:
tab[j], tab[j+1] = tab[j+1], tab[j]
return tab
```
- **Complexité temporelle :** O(n²)
### Conclusion
La compréhension de la complexité algorithmique est cruciale pour la conception d'algorithmes efficaces. En analysant les performances d'un algorithme, on peut choisir la meilleure approche pour résoudre un problème donné, en tenant compte des ressources disponibles.
Si vous avez besoin de plus d'exercices ou d'exemples spécifiques, n'hésitez pas à demander !
