Complexité temporelle et complexité spatiale

En général, la complexité temporelle et la complexité spatiale sont des moyens de mesurer l'efficacité d'un algorithme en fonction de la façon dont son utilisation des ressources évolue avec le taille de son entrée. Passons en revue les bases et quelques exemples courants.

Complexité temporelle

La complexité temporelle décrit le temps nécessaire à un algorithme pour s'exécuter en fonction de la taille de l'entrée (souvent notée n).

1. Temps constant – O(1) :

   • Le temps d'exécution de l'algorithme ne change pas avec la taille d'entrée.
   • Exemple : Accéder à un élément d'un tableau par index, comme dans arr[5].

2. Temps logarithmique – O(log n) :

   • Le temps d'exécution de l'algorithme augmente de manière logarithmique à mesure que la taille d'entrée augmente, ce qui signifie qu'il divise le problème en deux à chaque étape.
   • Exemple : Recherche binaire sur un tableau trié.

3. Temps linéaire – O(n) :

   • Le temps d'exécution de l'algorithme augmente linéairement avec la taille d'entrée.
   • Exemple : Parcourir un tableau de n éléments une fois.

4. Temps linéaire – O(n log n) :

   • Courant dans les algorithmes de tri efficaces où chaque élément est traité de manière logarithmique, généralement en raison d'une division récursive et d'une fusion ou d'un traitement linéaire.
   • Exemple : tri par fusion, tri rapide.

5. Temps quadratique – O(n²) :

   • Le temps d'exécution augmente proportionnellement au carré de la taille d'entrée.
   • Exemple : boucles imbriquées, telles que comparer chaque élément d'un tableau à tous les autres éléments.

6. Temps Cube – O(n³) :

   • Le temps d'exécution augmente avec le cube de la taille d'entrée. Rare mais peut se produire dans des algorithmes à trois boucles imbriquées.
   • Exemple : Résoudre certaines opérations matricielles à l'aide d'algorithmes de force brute.

7. Temps exponentiel – O(2^n) :

   • Le temps d'exécution double avec chaque élément supplémentaire dans l'entrée, généralement à partir d'algorithmes récursifs qui résolvent des sous-problèmes dans toutes les combinaisons possibles.
   • Exemple : La solution naïve pour la séquence de Fibonacci, où chaque appel mène à deux appels supplémentaires.

8. Temps factoriel – O(n!) :

   • Le temps d'exécution augmente de manière factorielle avec la taille de l'entrée. Souvent à partir d'algorithmes qui impliquent de générer toutes les permutations ou combinaisons possibles.
   • Exemple : Résoudre le problème du voyageur de commerce avec la force brute.

Complexité spatiale

La complexité spatiale mesure la quantité de mémoire utilisée par un algorithme par rapport à la taille d'entrée.

1. Espace constant – O(1) :

   • L'algorithme utilise une quantité fixe de mémoire quelle que soit la taille d'entrée.
   • Exemple : stocker quelques variables, comme des entiers ou des compteurs.

2. Espace logarithmique – O(log n) :

   • L'utilisation de la mémoire augmente de manière logarithmique, souvent observée avec des algorithmes récursifs qui réduisent de moitié le problème à chaque étape.
   • Exemple : recherche binaire récursive (complexité spatiale due à la pile d'appels).

3. Espace linéaire – O(n) :

   • L'utilisation de la mémoire augmente de manière linéaire avec la taille de l'entrée, ce qui est courant lors de la création d'un tableau ou d'une structure de données supplémentaire pour stocker l'entrée.
   • Exemple : Création d'une copie d'un tableau de taille n.

4. Espace quadratique – O(n²) :

   • L'utilisation de la mémoire augmente avec le carré de la taille d'entrée, par exemple lors du stockage d'une matrice 2D de taille n x n.
   • Exemple : Stockage d'une matrice de contiguïté pour un graphe à n nœuds.

5. Espace exponentiel – O(2^n) :

   • L'utilisation de la mémoire augmente de façon exponentielle avec la taille de l'entrée, souvent dans des solutions récursives qui stockent des données pour chaque sous-ensemble possible de l'entrée.
   • Exemple : mémorisation dans des algorithmes récursifs avec de nombreux sous-problèmes qui se chevauchent.

Exemples pratiques

• Temps linéaire (O(n)) et espace linéaire (O(n)) :

  • Une fonction qui parcourt un tableau et stocke chaque élément dans un nouveau tableau.

• Temps quadratique (O(n²)) et espace constant (O(1)) :

  • Une fonction qui comporte deux boucles imbriquées sur un tableau mais ne nécessite pas de stockage supplémentaire au-delà de quelques variables.

Analyser la complexité

Lors de l'analyse du code pour la complexité temporelle et spatiale :

1. Identifiez les boucles : Les boucles imbriquées augmentent généralement la complexité (par exemple, une boucle donne ( O(n) ); deux boucles imbriquées donnent ( O(n^2) )).
2. Recherchez la récursivité : les appels récursifs peuvent conduire à une complexité temporelle et spatiale exponentielle, en fonction du facteur de branchement et de la profondeur de la récursivité.
3. Considérez les structures de données : L'utilisation de structures de données supplémentaires telles que des tableaux, des listes ou des cartes de hachage peut affecter la complexité de l'espace.

Conseils généraux

• La La complexité temporelle consiste à compter les opérations en fonction de la taille de l'entrée.
• La La complexité spatiale consiste à compter la quantité de mémoire supplémentaire requise.

En évaluant ces facteurs, vous pouvez estimer l'efficacité avec laquelle un algorithme fonctionne et la quantité de mémoire qu'il consomme en fonction de la taille d'entrée.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!