Méthode de comptage des pas pour les boucles
Boucle for
Le coût est proportionnel au nombre d'itérations.
Exemple 1 : Boucle for simple
for (int i = 0; i < n; i++) {
printf("%d\n", i);
}for i in range(n):
print(i)Comptage des pas :
- Initialisation : 1 fois.
- Comparaison : n+1 fois.
- Incrémentation : n fois.
- Instruction : n fois.
Complexité totale = \(O(n)\)
Exemple 2 : Recherche du maximum
int max_val(int tab[], int n) {
int m = tab[0]; // O(1)
for (int i = 0; i < n; i++) { // n itérations
if (tab[i] > m) // n comparaisons
m = tab[i]; // au plus n affectations
}
return m; // O(1)
}def max_val(tab):
m = tab[0] # O(1)
for i in range(len(tab)): # n itérations
if tab[i] > m: # n comparaisons
m = tab[i] # au plus n affectations
return m # O(1)Complexité = \(O(n)\)
Boucle while
Pour une boucle for, le nombre d'itérations est généralement explicite (ex. for i in range(n) → exactement n tours).
Mais pour une boucle while, il faut estimer le nombre d'itérations :
- Identifier la variable de contrôle (celle qui change à chaque tour).
- Étudier la condition d'arrêt.
- Déterminer comment évolue la variable de contrôle.
- En déduire le nombre de tours possibles.
Exemple 1 : Incrémentation simple
int i = 0;
while (i < n) {
i++;
}i = 0
while i < n:
i += 1- Variable de contrôle :
i. - Condition d'arrêt :
i < n. - Évolution :
iaugmente de 1 à chaque tour. - Nombre d'itérations ≈ \(n\).
Complexité = \(O(n)\)
Exemple 2 : Multiplication par 2 (croissance géométrique)
int i = 1;
while (i < n) {
i *= 2;
}i = 1
while i < n:
i *= 2- Variable de contrôle : \(i\).
- Condition d'arrêt : \(i < n\).
- Évolution : \(i\) double à chaque tour.
- Après \(k\) tours : \(i = 2^k\).
- La boucle s'arrête quand \(2^k \ge n\).
\[ k \approx \log_2(n) \]
Complexité = \(O(\log n)\)
Exemple 3 : Décrémentation simple
int i = n;
while (i > 0) {
i--;
}i = n
while i > 0:
i -= 1- Variable de contrôle : \(i\).
- Condition d'arrêt : \(i > 0\).
- Évolution : \(i\) diminue de 1 à chaque tour.
- Nombre de tours = \(n\).
Complexité = \(O(n)\)
Exemple 4 : Division par 2 (décroissance géométrique)
int i = n;
while (i > 1) {
i /= 2;
}i = n
while i > 1:
i //= 2- Variable de contrôle : \(i\).
- Condition d'arrêt : \(i > 1\).
- Évolution : \(i\) est divisé par 2 à chaque tour.
- Après \(k\) tours : \(i = n / 2^k\).
- La boucle s'arrête quand \(n / 2^k \le 1\).
\[ k \approx \log_2(n) \]
Complexité = \(O(\log n)\)
Exemple 5 : Croissance quadratique
int p = 0;
int i = 0;
while (p < n) {
p += i;
i++;
}p = 0
i = 0
while p < n:
p += i
i += 1- Variables de contrôle : \(p\) et \(i\).
- Évolution :
- \(i\) croît linéairement.
- \(p\) croît comme la somme \(0 + 1 + 2 + \ldots + i = i(i+1)/2\).
- Condition d'arrêt : \(p \ge n\).
- Arrêt quand \(i^2 \approx n\).
\[ i \approx \sqrt{n} \]
Complexité = \(O(\sqrt{n})\)
Boucles imbriquées
Principe
- Identifier le nombre d'itérations de chaque boucle.
- Écrire la somme exacte.
- Simplifier avec des sommes connues :
- \(\sum_{i=1}^{n} 1 = n\)
- \(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\)
- \(\sum_{i=1}^{n} \log i = O(n \log n)\)
- \(\sum_{k=0}^{\lfloor \log_2 n \rfloor} 1 = O(\log n)\)
- Conclure en \(O(\cdot)\).
Exemple 1 : Boucles imbriquées indépendantes
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
operation(); // O(1)
}
}for i in range(n):
for j in range(n):
op() # O(1)Pour chaque \(i\), la boucle interne exécute exactement \(n\) opérations \(O(1)\).
\[ \sum_{i=1}^{n} \sum_{j=1}^{n} 1 = n \cdot n = n^2 \]
Complexité = \(O(n^2)\)
Exemple 2 : Boucles imbriquées dépendantes (de i à n)
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
operation(); // O(1)
}
}for i in range(n):
for j in range(i, n):
op() # O(1)Pour un \(i\) fixé : nombre d'itérations = \((n-1) - i + 1 = n - i\).
\[ \sum_{i=1}^{n} (n - i) = \underbrace{\sum_{i=1}^{n} n}_{=n^2} - \underbrace{\sum_{i=1}^{n} i}_{=n(n+1)/2} = n^2 - \frac{n(n+1)}{2} = \frac{n(n-1)}{2} \]
Complexité = \(O(n^2)\)
Exemple 3 : Boucles imbriquées dépendantes (de 0 à i-1)
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
operation(); // O(1)
}
}for i in range(n):
for j in range(i):
op() # O(1)\[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \]
Complexité = \(O(n^2)\)
Exemple 4 : Boucle for avec boucle while logarithmique
for (int i = 0; i < n; i++) {
int j = 1;
while (j <= n) {
operation(); // O(1)
j = j * 2;
}
}for i in range(n):
j = 1
while j <= n:
op() # O(1)
j = j * 2Pour un \(i\) fixé : \(\lfloor \log_2 n \rfloor + 1 = O(\log n)\) itérations.
\[ \sum_{i=1}^{n} O(\log i) = O\left(\sum_{i=1}^{n} \log i\right) = O(\log(n!)) = O(n \log n) \]
Complexité = \(O(n \log n)\)
Tableau récapitulatif
| Type de boucle | Code | Nombre d'itérations | Complexité |
|---|---|---|---|
| For simple | for i in range(n): op() | \(n\) | \(O(n)\) |
| While incrémental | while i < n: i++ | \(n\) | \(O(n)\) |
| While géométrique | while i < n: i *= 2 | \(\log_2 n\) | \(O(\log n)\) |
| Boucles imbriquées indépendantes | for i in range(n): for j in range(n): op() | \(n^2\) | \(O(n^2)\) |
| Boucles imbriquées dépendantes | for i in range(n): for j in range(i): op() | \(n(n-1)/2\) | \(O(n^2)\) |
| Boucle avec while logarithmique | for i in range(n): j=1; while j<=n: j*=2 | \(n \log n\) | \(O(n \log n)\) |
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.