Chapitre 911 minIntermédiaire
Les suites en informatique : complexité, stockage, trafic
Par Josselyn C., prof de BTS SIO. Mis à jour le .
À la fin de ce chapitre, tu sauras
- relier une complexité linéaire, quadratique, logarithmique ou exponentielle à une suite ;
- mesurer l'effet de la longueur d'un mot de passe sur une attaque par force brute ;
- prévoir la saturation d'un stockage ou d'un lien réseau ;
- calculer un temps de doublement.
4 exercices corrigés1 schéma
En informatique, les suites décrivent tout ce qui évolue par étapes : le nombre d'opérations d'un algorithme quand la taille des données augmente, le volume d'un stockage qui croît chaque année, le trafic d'un lien réseau, le nombre de mots de passe possibles quand on ajoute un caractère. Ce chapitre reprend ces situations avec les outils des chapitres précédents : reconnaître le type de suite, écrire le terme général, chercher un seuil. Ce sont des contextes fréquents dans les exercices de suites, et des raisonnements que tu tiendras en entreprise pour dimensionner une infrastructure.
Complexité : compter les opérations d'un algorithme
La complexité d'un algorithme mesure comment son nombre d'opérations augmente avec la taille n des données. On ne compte pas les secondes, qui dépendent de la machine, mais les opérations significatives : comparaisons, tours de boucle. Le vocabulaire (notation O) est présenté dans le cours d'algorithmique ; ici, on regarde les suites qui se cachent derrière.
Une boucle simple : une suite arithmétique. Un script d'inventaire interroge les n postes d'un parc, un par un : 3 secondes pour démarrer, puis 0,2 seconde par poste. Sa durée tₙ = 3 + 0,2n est une suite arithmétique de raison 0,2 : 5 s pour 10 postes, 23 s pour 100, 103 s pour 500. Ajouter un poste ajoute toujours le même temps. C'est une complexité linéaire.
Deux boucles imbriquées : la somme 1 + 2 + … + (n − 1). Pour détecter les doublons dans une liste de n adresses MAC, l'algorithme naïf compare chaque adresse à toutes les suivantes : n − 1 comparaisons pour la première, n − 2 pour la deuxième, et ainsi de suite jusqu'à 1. Le total est la somme d'une suite arithmétique (chapitre 4) :
(n − 1) + (n − 2) + … + 2 + 1 = n × (n − 1) / 2
| n | 10 | 100 | 1 000 | 1 000 000 |
|---|---|---|---|---|
| Comparaisons n(n − 1)/2 | 45 | 4 950 | 499 500 | ≈ 5 × 10¹¹ |
Multiplier la taille par 10 multiplie le travail par 100 environ : c'est une complexité quadratique, en n².
La recherche dichotomique : une suite géométrique de raison 1/2. Pour retrouver une valeur dans une liste triée, on regarde l'élément du milieu, et on élimine la moitié qui ne peut pas contenir la valeur. La taille de la zone de recherche forme une suite géométrique de raison 0,5 : zₖ = n × 0,5ᵏ après k étapes.
Pour 1 024 éléments, il reste un seul élément après 10 étapes, puisque 2¹⁰ = 1 024. Pour un million d'éléments, comme 2²⁰ = 1 048 576 dépasse un million, 20 étapes suffisent, contre un million de comparaisons pour une recherche élément par élément. Le nombre d'étapes est le seuil k tel que n × 0,5ᵏ ≤ 1, soit k ≥ log₂(n) : c'est une complexité logarithmique. C'est le principe des index des bases de données (cours SQL).
Tout essayer : une suite géométrique de raison 2. Un algorithme qui teste toutes les combinaisons de n options (chaque option activée ou non) en examine 2ⁿ. Chaque option ajoutée double le travail : 1 024 cas pour 10 options, plus d'un million pour 20, plus d'un milliard pour 30. C'est une complexité exponentielle, inutilisable au-delà de quelques dizaines d'éléments (chapitre 6).
| Croissance | Suite | Exemple | Pour n = 1 000 |
|---|---|---|---|
| Logarithmique | log₂(n) | Recherche dichotomique | ≈ 10 |
| Linéaire | arithmétique, a × n + b | Parcourir une liste | 1 000 |
| Quadratique | n², somme 1 + … + n | Comparer toutes les paires | ≈ 500 000 |
| Exponentielle | géométrique, 2ⁿ | Tester toutes les combinaisons | ≈ 10³⁰¹ |
Mots de passe et force brute
Une attaque par force brute essaie toutes les combinaisons possibles d'un mot de passe ; sa durée est proportionnelle au nombre de combinaisons. Avec un alphabet de A caractères, il y a A^L mots de passe de longueur L : pour une longueur qui augmente, c'est une suite géométrique de raison A.
| Longueur L | Minuscules seules (26ᴸ) | Lettres et chiffres (62ᴸ) |
|---|---|---|
| 8 | ≈ 2,09 × 10¹¹ | ≈ 2,18 × 10¹⁴ |
| 12 | ≈ 9,54 × 10¹⁶ | ≈ 3,23 × 10²¹ |
Passer de 8 à 12 caractères alphanumériques multiplie le nombre de combinaisons par 62⁴ ≈ 14,8 millions. C'est pourquoi les recommandations de l'ANSSI et de la CNIL insistent sur la longueur des mots de passe, et pourquoi les sites les stockent hachés avec une fonction lente (cours Authentification). Le TP Mots de passe et hygiène numérique te fait mesurer la force de tes propres mots de passe.
Stockage : prévoir la saturation
Reprenons le NAS de Sorbier Logistique (cours TrueNAS) : 9 TiB d'archives en 2026, + 25 % par an, plus 4,3 TiB de données stables. Avec un pool utilisable de 22,56 TiB, les archives ne doivent pas dépasser 18,26 TiB.
- Modèle : uₙ = 9 × 1,25ⁿ, géométrique de raison 1,25.
- Seuil : uₙ > 18,26 au rang 4 (u₃ ≈ 17,58 ; u₄ ≈ 21,97), soit en 2030 (chapitre 8).
- Décision : un second groupe de six disques porte la capacité utilisable à 45,11 TiB, soit 40,81 TiB pour les archives. Nouveau seuil : 9 × 1,25ⁿ > 40,81 au rang 7 (u₆ ≈ 34,33 ; u₇ ≈ 42,92), soit en 2033.
Doubler la capacité ne fait gagner que trois ans : avec une croissance de 25 % par an, le volume double en un peu plus de trois ans (1,25³ ≈ 1,95 ; 1,25⁴ ≈ 2,44). C'est la leçon des suites géométriques en dimensionnement : on ne repousse une croissance exponentielle que d'un temps fixe à chaque doublement de capacité.
Journaux et rétention : une suite arithmétique qui plafonne
Le serveur de journaux reçoit 12 Gio de journaux par jour, et la politique de rétention les conserve 90 jours. Pendant les 90 premiers jours, le volume est une suite arithmétique : 12, 24, 36… Au-delà, chaque jour, les journaux du jour le plus ancien sont supprimés quand ceux du jour arrivent : le volume reste à 12 × 90 = 1 080 Gio. Une suite n'a pas besoin d'une seule formule : elle peut être arithmétique puis constante, et c'est ce plafond qu'on dimensionne. Le cours Sauvegarde et PRA détaille les politiques de rétention.
Trafic réseau : quand faudra-t-il augmenter le débit ?
Sur le lien loué Lyon – Marseille de Sorbier, limité à 100 Mbit/s par le contrat (cours Routage et commutation), Zabbix mesure 45 Mbit/s aux heures de pointe en 2026. Le trafic augmente de 12 % par an : tₙ = 45 × 1,12ⁿ.
- Seuil d'alerte : au-delà de 80 % du débit, soit 80 Mbit/s, les temps de réponse se dégradent. t₅ ≈ 79,31 et t₆ ≈ 88,82 : le seuil est franchi en 2032.
- Saturation : t₇ ≈ 99,48 et t₈ ≈ 111,42 : le lien sature en 2034.
L'administrateur sait donc qu'il doit renégocier le contrat avant 2032 : c'est l'intérêt des graphiques de tendance de la supervision, qui prolongent les mesures passées.
La loi de Moore
En 1965, Gordon Moore, qui cofondera Intel trois ans plus tard, observe que le nombre de transistors sur une puce double chaque année ; en 1975, il corrige : un doublement tous les deux ans environ. Ce n'est pas une loi physique mais une tendance, vérifiée pendant des décennies et qui ralentit depuis les années 2010.
En comptant par périodes de deux ans, le nombre de transistors suit une suite géométrique de raison 2 : × 32 en dix ans (2⁵), × 1 024 en vingt ans (2¹⁰). Le coefficient annuel moyen est la racine carrée de 2 (chapitre 3) : √2 ≈ 1,414, soit environ + 41 % par an.
Exercices
Exercice 1 sur 4 Combien de comparaisons ? Réussi À revoir
Un script compare chaque compte d'un annuaire de n comptes à tous les suivants pour détecter les doublons d'adresse électronique.
- Combien de comparaisons fait-il pour 50 comptes ? pour 500 ?
- Par combien le nombre de comparaisons est-il multiplié quand l'annuaire passe de 500 à 5 000 comptes ?
Voir la réponseMasquer la réponse de l'exercice 1
- n(n − 1)/2 : pour 50 comptes, 50 × 49 / 2 = 1 225 ; pour 500, 500 × 499 / 2 = 124 750.
- Pour 5 000 : 5 000 × 4 999 / 2 = 12 497 500. Le rapport vaut 12 497 500 / 124 750 ≈ 100,2 : multiplier la taille par 10 multiplie le travail par 100 environ, signe d'une complexité quadratique. Trier d'abord la liste, puis comparer chaque adresse à sa voisine, éviterait ce coût.
Tu avais trouvé ?
Exercice 2 sur 4 Recherche dichotomique Réussi À revoir
Une table triée contient 50 000 tickets.
- Combien d'éléments reste-t-il au plus dans la zone de recherche après 5 étapes ? après 10 ?
- Combien d'étapes faut-il au plus pour qu'il ne reste qu'un élément ?
Voir la réponseMasquer la réponse de l'exercice 2
- La zone est divisée par 2 à chaque étape : 50 000 × 0,5⁵ = 1 562,5, soit au plus 1 563 éléments ; 50 000 × 0,5¹⁰ ≈ 48,8, soit au plus 49 éléments.
- On cherche le plus petit k tel que 50 000 × 0,5ᵏ ≤ 1, c'est-à-dire 2ᵏ ≥ 50 000. 2¹⁵ = 32 768 ne suffit pas, 2¹⁶ = 65 536 convient : 16 étapes. Une recherche élément par élément en ferait jusqu'à 50 000.
Tu avais trouvé ?
Exercice 3 sur 4 La longueur d'un mot de passe Réussi À revoir
Un mot de passe est composé de lettres minuscules, de lettres majuscules et de chiffres (62 caractères possibles).
- Par combien est multiplié le nombre de mots de passe possibles quand on ajoute un caractère ? quatre caractères ?
- Un code PIN de 4 chiffres et un mot de passe de 4 caractères alphanumériques : combien de combinaisons chacun ?
Voir la réponseMasquer la réponse de l'exercice 3
- Les nombres de mots de passe de longueur L forment une suite géométrique de raison 62 : un caractère de plus multiplie par 62, quatre caractères par 62⁴ = 14 776 336.
- PIN : 10⁴ = 10 000 combinaisons. Mot de passe : 62⁴ = 14 776 336 combinaisons. Un code PIN n'est acceptable que parce que l'appareil bloque après quelques essais ratés : sans ce blocage, 10 000 essais se font en un instant.
Tu avais trouvé ?
Exercice 4 sur 4 Le stockage des sauvegardes Réussi À revoir
Un serveur de sauvegarde contient 6 TiB en 2026, et le volume augmente de 18 % par an. Sa capacité utile est de 15 TiB.
- Écris le volume vₙ l'année 2026 + n.
- En quelle année la capacité sera-t-elle dépassée ? Donne les deux termes qui encadrent le seuil.
- On double la capacité (30 TiB). Combien d'années gagne-t-on ?
Voir la réponseMasquer la réponse de l'exercice 4
- vₙ = 6 × 1,18ⁿ.
- v₅ ≈ 13,73 et v₆ ≈ 16,20 : la capacité est dépassée en 2032 (rang 6).
- Avec 30 TiB : v₉ ≈ 26,61 et v₁₀ ≈ 31,40, dépassement en 2036 (rang 10). On gagne 4 ans, environ le temps de doublement d'une croissance de 18 % (1,18⁴ ≈ 1,94, 1,18⁵ ≈ 2,29). Par le calcul : ln(2) / ln(1,18) ≈ 4,19.
Tu avais trouvé ?