Comprendre la complexité algorithmique, et en particulier la notation Big-O, est crucial pour analyser et comparer l’efficacité des algorithmes. En C++, comme dans les autres langages de programmation, la complexité d’un algorithme peut affecter significativement les performances et l’évolutivité d’une application. Il est donc utile de savoir comment améliorer la complexité algorithmique. Mais d’abord, explorons les classes de complexité les plus courantes :
1. O(1) - Temps constant
Exemple : Accéder à un élément d’un tableau par son indice.
#include <iostream>
int main() {
int arr[] = {1, 2, 3, 4, 5};
int index = 2;
std::cout << "Element at index " << index << " is " << arr[index] << std::endl; // O(1) operation
return 0;
}2. O(log n) - Temps logarithmique
Exemple : La recherche binaire dans un tableau trié.
#include <iostream>
#include <vector>
#include <algorithm>
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
int main() {
std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 7;
int result = binarySearch(arr, target);
if (result != -1)
std::cout << "Element found at index " << result << std::endl;
else
std::cout << "Element not found" << std::endl;
return 0;
}3. O(n) - Temps linéaire
Exemple : Additionner les éléments d’un tableau.
#include <iostream>
int sumArray(const int arr[], int size) {
int sum = 0;
for (int i = 0; i < size; ++i) {
sum += arr[i];
}
return sum;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Sum of array elements is " << sumArray(arr, size) << std::endl;
return 0;
}4. O(n log n) - Temps linéarithmique
Exemple : L’algorithme du tri fusion.
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int i = 0; i < n2; ++i)
R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.size() - 1);
for (int x : arr) std::cout << x << " ";
std::cout << std::endl;
return 0;
}5. O(n^2) - Temps quadratique
Exemple : L’algorithme du tri à bulles.
#include <iostream>
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
for (int j = 0; j < size - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
int arr[] = {5, 1, 4, 2, 8};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
for (int i = 0; i < size; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
return 0;
}6. O(n^3) - Temps cubique
Exemple : Vérifier si trois nombres d’un tableau totalisent une somme donnée.
#include <iostream>
bool findTriplet(int arr[], int n, int sum) {
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
for (int k = j + 1; k < n; ++k) {
if (arr[i] + arr[j] + arr[k] == sum) {
std::cout << "Triplet found: " << arr[i] << ", " << arr[j] << ", " << arr[k] << std::endl;
return true;
}
}
}
}
return false;
}
int main() {
int arr[] = {1, 4, 45, 6, 10, 8};
int sum = 22;
int size = sizeof(arr) / sizeof(arr[0]);
if (!findTriplet(arr, size, sum))
std::cout << "No triplet found" << std::endl;
return 0;
}7. O(2^n) - Temps exponentiel
Exemple : Le calcul récursif des nombres de Fibonacci.
#include <iostream>
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 5;
std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
return 0;
}8. O(n!) - Temps factoriel
Exemple : Générer toutes les permutations d’une chaîne.
#include <iostream>
#include <string>
#include <algorithm>
void permute(std::string str, int l, int r) {
if (l == r) {
std::cout << str << std::endl;
} else {
for (int i = l; i <= r; ++i) {
std::swap(str[l], str[i]);
permute(str, l + 1, r);
std::swap(str[l], str[i]); // backtrack
}
}
}
int main() {
std::string str = "ABC";
permute(str, 0, str.size() - 1);
return 0;
}Conseils pour optimiser la complexité Big-O
Optimiser la complexité algorithmique implique souvent d’utiliser différentes techniques pour réduire la complexité en temps ou en espace d’un algorithme. Voici quelques techniques courantes :
1. Choisir les bonnes structures de données
Choisir les bonnes structures de données est crucial pour optimiser la complexité Big-O de vos algorithmes. Différentes structures offrent différentes efficacités pour des opérations variées comme l’insertion, la suppression, l’accès et la recherche. Ci-dessous, nous abordons plusieurs structures de données courantes et leurs opérations typiques, avec des exemples C++ pour chacune.
1. 1 Les tableaux
Propriétés :
- Taille fixe
- Allocation mémoire contiguë
- Accès rapide par indice (O(1))
- Insertions et suppressions lentes (O(n))
Cas d’usage : À utiliser quand le nombre d’éléments est connu à l’avance et qu’un accès rapide par indice est requis.
Exemple C++ :
#include <iostream>
int main() {
int arr[] = {1, 2, 3, 4, 5};
int index = 2;
std::cout << "Element at index " << index << " is " << arr[index] << std::endl; // O(1) access
return 0;
}1.2. Les listes chaînées
Propriétés :
- Taille dynamique
- Allocation mémoire non contiguë
- Insertions et suppressions rapides (O(1) si la position est connue)
- Accès lent par indice (O(n))
Cas d’usage : À utiliser quand le nombre d’éléments est inconnu ou variable et que des insertions ou suppressions fréquentes sont nécessaires.
Exemple C++ :
#include <iostream>
struct Node {
int data;
Node* next;
};
void append(Node*& head, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = nullptr;
if (!head) {
head = new_node;
return;
}
Node* last = head;
while (last->next) {
last = last->next;
}
last->next = new_node;
}
void printList(Node* node) {
while (node) {
std::cout << node->data << " ";
node = node->next;
}
std::cout << std::endl;
}
int main() {
Node* head = nullptr;
append(head, 1);
append(head, 2);
append(head, 3);
printList(head); // O(n) traversal
return 0;
}1.3. Les tables de hachage (unordered_map)
Propriétés :
- Complexité temporelle moyenne en O(1) pour les insertions, suppressions et accès
- Taille dynamique
- Allocation mémoire non contiguë
Cas d’usage : À utiliser quand des accès, insertions et suppressions rapides sont requis et que l’ordre des éléments importe peu.
Exemple C++ :
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> umap;
umap["one"] = 1;
umap["two"] = 2;
umap["three"] = 3;
std::cout << "Value for key 'two': " << umap["two"] << std::endl; // O(1) access
return 0;
}1.4. Les arbres équilibrés (par ex. std::map, std::set)
Propriétés :
- Complexité temporelle en O(log n) pour les insertions, suppressions et accès
- Les éléments restent triés
Cas d’usage : À utiliser quand les éléments doivent rester triés et que des insertions, suppressions et accès relativement rapides sont nécessaires.
Exemple C++ :
#include <iostream>
#include <map>
int main() {
std::map<std::string, int> omap;
omap["one"] = 1;
omap["two"] = 2;
omap["three"] = 3;
std::cout << "Value for key 'two': " << omap["two"] << std::endl; // O(log n) access
for (const auto& pair : omap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}1.5. Les tas (file de priorité)
Propriétés :
- Complexité temporelle en O(log n) pour les insertions et suppressions
- Complexité en O(1) pour l’accès à l’élément maximal/minimal
Cas d’usage : À utiliser pour des ensembles de données évolutifs lorsque vous devez fréquemment accéder au plus grand ou au plus petit élément.
Exemple C++ :
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
std::cout << "Top element is " << pq.top() << std::endl; // O(1) access to the maximum element
pq.pop(); // O(log n) deletion
std::cout << "Top element after pop is " << pq.top() << std::endl;
return 0;
}1.6. Les graphes
Propriétés :
- Représentés sous forme de listes ou de matrices d’adjacence
- Liste d’adjacence : O(V + E) pour le parcours
- Matrice d’adjacence : O(V^2) pour le parcours
Cas d’usage : À utiliser pour représenter des relations ou connexions entre entités, comme les réseaux sociaux ou les réseaux de transport.
Exemple C++ (liste d’adjacence) :
#include <iostream>
#include <vector>
void addEdge(std::vector<int> adj[], int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // For undirected graph
}
void printGraph(const std::vector<int> adj[], int V) {
for (int v = 0; v < V; ++v) {
std::cout << "Adjacency list of vertex " << v << "\n head ";
for (auto x : adj[v]) std::cout << "-> " << x;
std::cout << std::endl;
}
}
int main() {
int V = 5;
std::vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
printGraph(adj, V);
return 0;
}2. Diviser pour régner
Divise le problème en sous-problèmes plus petits, résout chacun récursivement, puis combine les solutions, comme :
- Le tri fusion : Divise le tableau en deux moitiés, trie chaque moitié et fusionne les moitiés triées, pour une complexité en O(n log n).
- Le tri rapide : Divise le tableau en sous-tableaux autour d’un pivot et trie les sous-tableaux, avec une complexité moyenne en O(n log n).
3. La mémoïsation
- Une technique d’optimisation qui stocke les résultats d’appels de fonctions coûteux et les réutilise lorsque les mêmes entrées se reproduisent.
- Souvent utilisée conjointement avec les algorithmes récursifs pour améliorer l’efficacité.
- Exemple : le calcul récursif de Fibonacci avec mémoïsation réduit la complexité de O(2^n) à O(n).
#include <iostream>
#include <vector>
int fibonacci(int n, std::vector<int>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
int main() {
int n = 30;
std::vector<int> memo(n + 1, -1);
std::cout << "Fibonacci of " << n << " is " << fibonacci(n, memo) << std::endl;
return 0;
}4. Le précalcul et la mise en cache
- Précalculez les résultats pour les entrées possibles et stockez-les pour un accès rapide pendant l’exécution.
- Exemple des tableaux de sommes préfixes : Permet des requêtes de somme sur un intervalle en O(1) après un prétraitement en O(n).
#include <iostream>
#include <vector>
std::vector<int> computePrefixSum(const std::vector<int>& nums) {
std::vector<int> prefixSum(nums.size());
prefixSum[0] = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
prefixSum[i] = prefixSum[i - 1] + nums[i];
}
return prefixSum;
}
int rangeSum(const std::vector<int>& prefixSum, int left, int right) {
if (left == 0) return prefixSum[right];
return prefixSum[right] - prefixSum[left - 1];
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
std::vector<int> prefixSum = computePrefixSum(nums);
int left = 1, right = 3;
std::cout << "Sum of range [" << left << ", " << right << "] is " << rangeSum(prefixSum, left, right) << std::endl;
return 0;
}5. L’optimisation du tri et de la recherche
- Choisissez les algorithmes de tri en fonction des caractéristiques de l’entrée (par exemple Timsort pour les données du monde réel).
- Utilisez des algorithmes de recherche efficaces comme la recherche binaire (O(log n)) pour les données triées.
#include <iostream>
#include <vector>
#include <algorithm>
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
int main() {
std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 7;
std::cout << "Index of " << target << " is " << binarySearch(arr, target) << std::endl;
return 0;
}6. Les compromis espace-temps
Les compromis espace-temps consistent à équilibrer l’usage mémoire et la vitesse d’exécution. Dans certains cas, vous pouvez réduire la complexité temporelle d’un algorithme en utilisant plus de mémoire, ou inversement. Voici un exemple C++ illustrant ce concept avec la suite de Fibonacci.
6.1. L’approche récursive naïve (temps non optimisé, espace inefficace)
L’approche récursive naïve du calcul des nombres de Fibonacci a une complexité temporelle exponentielle en O(2^n) et consomme beaucoup d’espace de pile, car elle recalcule sans cesse les mêmes valeurs.
Code :
#include <iostream>
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 30; // Be careful with large values of n as it will take significant time
std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
return 0;
}6.2. Programmation dynamique avec mémoïsation (temps optimisé, espace optimisé)
La mémoïsation stocke les résultats déjà calculés, réduisant la complexité temporelle à O(n) au prix d’une mémoire supplémentaire.
Code :
#include <iostream>
#include <vector>
int fibonacci(int n, std::vector<int>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
int main() {
int n = 30;
std::vector<int> memo(n + 1, -1);
std::cout << "Fibonacci of " << n << " is " << fibonacci(n, memo) << std::endl;
return 0;
}6.3. Approche itérative (temps efficace, espace efficace)
L’approche itérative calcule les nombres de Fibonacci avec une complexité temporelle en O(n) et spatiale en O(1).
Code :
#include <iostream>
int fibonacci(int n) {
if (n <= 1) return n;
int prev2 = 0, prev1 = 1, current;
for (int i = 2; i <= n; ++i) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
int main() {
int n = 30;
std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
return 0;
}Explication des compromis espace-temps
1. Approche récursive naïve :
- Complexité temporelle : O(2^n), car elle recalcule les nombres de Fibonacci de nombreuses fois.
- Complexité spatiale : O(n) en raison de la pile d’appels utilisée par la récursion.
2. Programmation dynamique avec mémoïsation :
- Complexité temporelle : O(n), car elle ne calcule chaque nombre de Fibonacci qu’une seule fois.
- Complexité spatiale : O(n) pour stocker les résultats des calculs précédents dans un tableau de mémoïsation.
3. Approche itérative :
- Complexité temporelle : O(n) pour calculer la suite de Fibonacci.
- Complexité spatiale : O(1), car elle n’utilise que quelques variables pour stocker les résultats intermédiaires.
7. Le parallélisme et la concurrence
- Répartissez le travail sur plusieurs processeurs ou threads pour réduire le temps d’exécution.
- Exemples :
- MapReduce : Un framework pour traiter de grands ensembles de données à l’aide d’un algorithme distribué sur un cluster.
- Les algorithmes de tri parallèles : Comme le tri fusion parallèle.
En employant ces techniques, vous pouvez souvent améliorer significativement l’efficacité de vos algorithmes, rendant vos applications plus rapides et plus évolutives.
Conclusion
La notation Big-O est un concept fondamental pour comprendre et analyser l’efficacité des algorithmes en C++. En offrant une vue de haut niveau du taux de croissance d’un algorithme, elle permet aux développeurs de prévoir les performances, de garantir l’évolutivité et d’optimiser leur code efficacement. Lors de la conception et de l’implémentation d’algorithmes, considérez toujours leur complexité Big-O pour prendre des décisions éclairées sur leur adéquation et leur efficacité au problème donné.