Bases des algorithmes
Un algorithme est un ensemble clair et fini d'étapes pour résoudre un problème spécifique.
Comprendre les concepts de base des algorithmes et les méthodes d'analyse d'efficacité est un prérequis important pour apprendre les structures de données et les algorithmes.
Définition et caractéristiques des algorithmes
En informatique, un algorithme est une séquence finie d'instructions, dont chacune représente une ou plusieurs opérations.
Un algorithme valide doit posséder les cinq caractéristiques de base suivantes :
| Caractéristique | Signification | Contre-exemple |
|---|---|---|
| Entrée | Il existe zéro ou plusieurs entrées externes | L'absence d'entrée est aussi valide, comme la génération de nombres aléatoires |
| Sortie | Produit au moins un résultat | Un « algorithme » sans aucune sortie n'a aucun sens |
| Définition | La signification de chaque étape doit être claire et sans ambiguïté | Les descriptions vagues comme « augmenter de manière appropriée » sont inacceptables |
| Finitude | Doit se terminer en un nombre fini d'étapes ; il ne peut pas boucler indéfiniment | Un système d'exploitation lui-même n'est pas un algorithme car il s'exécute théoriquement pour toujours |
| Faisabilité | Chaque étape peut être mise en œuvre à l'aide d'opérations de base | « Diviser par zéro » est infaisable, et « trier en une seule étape » l'est aussi |
La « finitude » d'un algorithme ne contredit pas la « boucle infinie » d'un programme. Un programme peut tomber dans une boucle infinie à cause d'un bug, mais un algorithme lui-même doit se terminer en un nombre fini d'étapes. La différence est : un algorithme est un concept au niveau de l'« intention de conception », tandis qu'un programme est un concept au niveau de l'« exécution réelle ».
Méthodes de représentation des algorithmes
Lors de la conception et de la communication d'algorithmes, deux méthodes de représentation sont couramment utilisées.
Pseudo-code
Le pseudo-code utilise un texte proche du langage naturel mais avec un certain format structuré pour décrire la logique d'un algorithme.
Il ne dépend de la syntaxe d'aucun langage de programmation spécifique, ce qui facilite l'expression rapide d'idées.
Par exemple, le pseudo-code pour trouver la valeur maximale dans un ensemble de nombres :
算法：FindMax 输入：数组 A，长度 n 输出：A 中的最大值 1. max = A[0] 2. for i = 1 to n-1: 3. if A[i] > max: 4. max = A[i] 5. return max
Organigramme
Un organigramme affiche visuellement le processus d'exécution d'un algorithme au moyen de graphiques.
La figure ci-dessus montre le processus d'exécution complet de l'algorithme FindMax : en partant du tableau d'entrée, initialiser le maximum actuel, puis comparer chaque élément tour à tour, mettre à jour le maximum si une valeur plus grande est trouvée, et afficher le résultat une fois le parcours terminé.
Conventions de symboles dans les organigrammes :
| Forme du symbole | Signification |
|---|---|
| Rectangle arrondi (ou ellipse) | Début / Fin |
| Rectangle | Étape de traitement |
| Losange | Décision / Branchement |
| Parallélogramme | Entrée / Sortie |
| Flèche | Sens du flux |
Analyse de l'efficacité des algorithmes
Après avoir conçu un algorithme, son efficacité doit également être évaluée. Elle se mesure principalement selon deux dimensions.
Complexité temporelle
La complexité temporelle décrit la tendance de croissance du nombre d'opérations de base requises par l'algorithme lorsque la taille d'entrée n augmente.
Notez que nous nous intéressons à la « tendance de croissance » plutôt qu'au « nombre exact d'exécutions ». Car pour des entrées à grande échelle, les différences de multiples constants sont bien moins importantes que les différences de tendances de croissance.
Complexité spatiale
La complexité spatiale décrit la tendance de croissance de l'espace mémoire supplémentaire requis pendant l'exécution d'un algorithme lorsque la taille de l'entrée n augmente.
L'accent mis sur l'espace « supplémentaire » ici signifie la quantité d'espace auxiliaire dont l'algorithme a besoin en plus de l'espace utilisé pour stocker les données d'entrée elles-mêmes.
Le temps et l'espace forment souvent une paire de compromis — échanger de l'espace contre du temps, ou échanger du temps contre de l'espace, est une stratégie de compromis courante dans la conception d'algorithmes. Par exemple : une table de hachage utilise de l'espace de stockage supplémentaire en échange d'un temps de recherche en O(1) ; tandis que les algorithmes de tri en place utilisent légèrement plus d'étapes de calcul pour éviter une consommation d'espace supplémentaire.
Notation Grand O
Notation Grand OC'est l'outil mathématique le plus couramment utilisé pour mesurer la complexité temporelle et la complexité spatiale.
Elle décrit la borne supérieure de la tendance de croissance du temps d'exécution ou de l'utilisation de l'espace lorsque la taille d'entrée n augmente, dans le pire des cas pour un algorithme.
Définition : S'il existe des constantes positives c et n0 telles que pour tout n ≥ n0, T(n) ≤ c × f(n), alors on le noteT(n) = O(f(n))。
Compréhension intuitive : la notation Grand O ignore les facteurs constants et les termes d'ordre inférieur, en se concentrant uniquement sur le terme qui croît le plus vite.
Par exemple : si un algorithme nécessite 3n² + 100n + 500 opérations, lorsque n est suffisamment grand, le terme n² domine la croissance, donc on dit qu'il est O(n²).
Niveaux de complexité courants
La figure ci-dessus montre intuitivement comment chaque niveau de complexité évolue lorsque la taille de l'entrée n augmente.
| Notation | Name | n=10 | n=1000 | Algorithmes typiques |
|---|---|---|---|---|
| O(1) | Ordre constant | 1 | 1 | Accès à un tableau par index, recherche dans une table de hachage |
| O(log n) | Ordre logarithmique | ~3 | ~10 | Recherche binaire, opérations sur un ABR équilibré |
| O(n) | Ordre linéaire | 10 | 1000 | Recherche linéaire, parcours d’un tableau |
| O(n log n) | Ordre linéarithmique | ~30 | ~10000 | Tri fusion, tri rapide (en moyenne) |
| O(n²) | Ordre quadratique | 100 | 1000000 | Tri à bulles, tri par sélection |
| O(2ⁿ) | Ordre exponentiel | 1024 | Nombre astronomique | Résolution par force brute de problèmes de sous-ensembles |
D'après le tableau, on peut voir que lorsque n=1000, O(1) ne nécessite toujours que 1 opération, O(n) nécessite 1000 opérations, et O(n²) nécessite 1 million d'opérations.
Dans les scénarios de données à grande échelle, choisir un algorithme avec une complexité appropriée peut entraîner des différences de performance de plusieurs ordres de grandeur.
En programmation réelle, essayez de faire en sorte que la complexité des algorithmes centraux ne dépasse pas O(n log n). Lorsque la complexité atteint O(n²) ou plus, il faut accorder une attention particulière à la question de savoir si la taille de l'entrée est contrôlable et s'il existe de meilleures alternatives.
Exemples de calcul de complexité temporelle
Voici un extrait de code C simple et son analyse de complexité temporelle :
Exemple
/* Fonction : calculer la somme des éléments du tableau
Complexité temporelle : O(n)
n est la longueur du tableau, la boucle s'exécute n fois, et chaque itération effectue un nombre constant d'opérations */
int sumArray(int arr[], int n) {
int total = 0; /* O(1) — opération d'affectation, exécutée une fois */
for (int i = 0; i < n; i++) { /* Corps de boucle */
total += arr[i]; /* O(1) — addition et affectation, exécutées n fois */
}
return total; /* O(1) — opération de retour, exécutée une fois */
}
/* Complexité temporelle globale : O(1 + n + 1) = O(n)
Les termes constants d'ordre inférieur sont ignorés */
int main() {
int nums[] = {5, 10, 15, 20, 25};
int size = sizeof(nums) / sizeof(nums[0]);
int result = sumArray(nums, size);
printf("Somme des éléments du tableau : %d\n", result); /* Sortie : Somme des éléments du tableau : 75 */
return 0;
}
Voyons maintenant un autre exemple avec des boucles imbriquées :
Exemple
/* Fonction : afficher une table de multiplication n×n
Complexité temporelle : O(n²)
La boucle externe s'exécute n fois, la boucle interne s'exécute n fois, pour un total de n×n fois */
void printMulTable(int n) {
for (int i = 1; i <= n; i++) { /* Boucle externe O(n) */
for (int j = 1; j <= n; j++) { /* Boucle interne O(n), total n² itérations après imbrication */
printf("%d\t", i * j); /* Opération O(1) */
}
printf("\n");
}
}
/* Complexité temporelle globale : O(n × n) = O(n²) */
int main() {
printMulTable(5); /* Affiche une table de multiplication 5×5 */
return 0;
}
Exemples de calcul de complexité spatiale
La complexité spatiale se concentre sur l'espace mémoire supplémentaire alloué pendant l'exécution d'un algorithme.
Exemple
#include <stdlib.h> /* Fichier d'en-tête pour malloc/free */
/* Fonction : créer un nouveau tableau stockant les carrés du tableau d'origine
Complexité spatiale : O(n) — alloue un nouveau tableau de longueur n */
int* squareArray(int arr[], int n) {
int* result = (int*)malloc(n * sizeof(int)); /* Allouer de l'espace supplémentaire pour n entiers */
if (result == NULL) {
return NULL; /* Renvoyer NULL si malloc échoue */
}
for (int i = 0; i < n; i++) {
result[i] = arr[i] * arr[i];
}
return result;
}
/* Complexité spatiale O(n) :
- Le tableau d'entrée arr n'est pas compté (il fait partie de l'entrée elle-même)
- Le tableau de résultat alloue en plus n entiers, ce qui représente de l'espace supplémentaire
- La variable i utilise un espace constant O(1), dominé par O(n) */
int main() {
int nums[] = {1, 2, 3, 4, 5};
int n = 5;
int* squared = squareArray(nums, n);
if (squared != NULL) {
for (int i = 0; i < n; i++) {
printf("%d ", squared[i]); /* Sortie : 1 4 9 16 25 */
}
printf("\n");
free(squared); /* Libérer manuellement la mémoire allouée dynamiquement */
}
return 0;
}
Autres extensionsIdées fausses courantes chez les débutants : la complexité temporelle et la complexité spatiale analysent les « tendances de croissance » plutôt que des valeurs exactes. Les coefficients constants, les termes d'ordre inférieur et les différences entre langages de programmation sont tous ignorés par la notation Big O. Par conséquent, O(2n) et O(n) sont équivalents — ils représentent tous deux une croissance linéaire.