Classification des algorithmes et exemples

La classification des algorithmes aide à sélectionner l'algorithme le plus approprié pour une tâche spécifique, permettant aux développeurs d'optimiser leur code et d'obtenir de meilleures performances. En informatique, un algorithme est un ensemble d’instructions bien défini utilisé pour résoudre un problème ou effectuer une tâche spécifique. L'efficience et l'efficacité de ces algorithmes sont essentielles pour déterminer la performance globale du programme.

Dans cet article, nous aborderons deux manières courantes de classer les algorithmes, à savoir en fonction de la complexité temporelle et en fonction des techniques de conception.

Grammaire

La syntaxe de la fonction main est utilisée dans le code des deux méthodes -

int main() {
   // Your code here
}

Algorithme

• Identifiez le problème à résoudre.

• Choisissez des méthodes appropriées pour classer les algorithmes.

• Écrivez du code en C++ en utilisant la méthode de votre choix.

• Compilez et exécutez le code.

• Analyser la sortie.

Quelle est la complexité temporelle ?

La complexité temporelle est une mesure du temps nécessaire à l'exécution d'un algorithme en fonction de la taille de l'entrée. C'est une manière de décrire l'efficacité d'un algorithme et son évolutivité à mesure que la taille de l'entrée augmente.

La complexité temporelle est généralement exprimée en notation grand O, qui donne une limite supérieure sur le temps d'exécution de l'algorithme. Par exemple, un algorithme avec une complexité temporelle de O(1) signifie que le temps d'exécution reste constant quelle que soit la taille de l'entrée, tandis qu'un algorithme avec une complexité temporelle de O(n^2) signifie que le temps d'exécution augmente quadratiquement avec la taille d'entrée. Comprendre la complexité temporelle d'un algorithme est important pour choisir le bon algorithme pour résoudre un problème et pour comparer différents algorithmes.

Méthode 1 : Classer les algorithmes en fonction de la complexité temporelle

Cette approche couvre la classification des algorithmes en fonction de leur complexité temporelle.

Cela nécessite d'abord d'interpréter la complexité de durée de l'algorithme, puis de le classer dans l'une des cinq catégories en fonction de sa complexité de temps écoulé : O(1) complexité temporelle constante, O(log n) propriété de complexité temporelle logarithmique, O(n) complexité temporelle linéaire, complexité temporelle quadratique O(n^2) ou complexité temporelle exponentielle O(2^n). Cette classification révèle l'efficacité de l'algorithme, et la taille des données d'entrée et le temps d'exécution prévu peuvent être pris en compte lors de la sélection d'un algorithme.

La traduction chinoise de

Exemple-1

est :

Exemple-1

Le code ci-dessous montre une démonstration de l'algorithme de recherche linéaire, qui a une complexité temporelle linéaire de O(n). Cet algorithme effectue une vérification systématique des éléments d'un tableau pour déterminer s'ils correspondent à un élément de recherche spécifié. Une fois trouvée, la fonction renvoie l'index de l'élément, sinon elle renvoie -1, indiquant que l'élément n'est pas dans le tableau. La fonction principale commence par initialiser le tableau et rechercher des éléments, appeler la fonction LinearSearch et enfin restituer les résultats.

<int>#include <iostream>
#include <vector>
#include <algorithm>
// Linear search function with linear time complexity O(n)
int linearSearch(const std::vector<int>& arr, int x) {
    for (size_t i = 0; i < arr.size(); i++) {
        if (arr[i] == x) {
            return static_cast<int>(i);
        }
    }
    return -1;
}
int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int search_element = 5;
    int result = linearSearch(arr, search_element);
    if (result != -1) {
        std::cout << "Element found at index: " << result << std::endl;
    } else {
        std::cout << "Element not found in the array." << std::endl;
    }
    return 0;
}
</int>

Sortie

Element found at index: 4

Méthode 2 : Classer les algorithmes en fonction des techniques de conception.

• Compétences en conception d'algorithmes d'analyse.

• Classez les algorithmes dans l'une des catégories suivantes −

  • Algorithme de force brute

  • Algorithme Diviser et Conquérir

  • Algorithme gourmand

  • Algorithme de programmation dynamique

  • Algorithme de retour en arrière

La traduction chinoise de

Exemple-2

est :

Exemple-2

Le programme suivant montre l'implémentation de l'algorithme de recherche binaire, qui utilise la stratégie diviser pour régner et a une complexité temporelle logarithmique O (log n). L'algorithme divise à plusieurs reprises le tableau en deux parties et vérifie l'élément du milieu. Si cet élément intermédiaire est égal à l'élément de recherche recherché, l'index est renvoyé immédiatement. Si l'élément du milieu dépasse l'élément recherché, la recherche continue dans la moitié gauche du tableau, si l'élément du milieu est plus petit, la recherche se poursuit dans la moitié droite. La fonction principale initialise le tableau et recherche les éléments, organise le tableau par tri, appelle la fonction binaireSearch et présente enfin les résultats.

#include <iostream>
#include <vector>
#include <algorithm>

// Binary search function using divide and conquer technique with logarithmic time complexity O(log n)
int binarySearch(const std::vector<int>& arr, int left, int right, int x) {
   if (right >= left) {
      int mid = left + (right - left) / 2;

      if (arr[mid] == x) {
         return mid;
      }

      if (arr[mid] > x) {
         return binarySearch(arr, left, mid - 1, x);
      }

      return binarySearch(arr, mid + 1, right, x);
   }
   return -1;
}

int main() {
   std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
   int search_element = 5;

   // The binary search algorithm assumes that the array is sorted.
   std::sort(arr.begin(), arr.end());

   int result = binarySearch(arr, 0, static_cast<int>(arr.size()) - 1, search_element);

   if (result != -1) {
      std::cout << "Element found at index: " << result <<std::endl;
   } else {
      std::cout << "Element not found in the array." << std::endl;
   }
   return 0;
}

Sortie

Element found at index: 4

Conclusion

Ainsi, dans cet article, deux méthodes de classification des algorithmes sont abordées : en fonction de leur complexité temporelle et en fonction de leurs méthodes de conception. À titre d'exemples, nous avons introduit un algorithme de recherche linéaire et un algorithme de recherche binaire, tous deux implémentés en C++. L'algorithme de recherche linéaire utilise une méthode de force brute et a une complexité temporelle linéaire de O(n), tandis que l'algorithme de recherche binaire utilise la méthode diviser pour régner et présente une complexité temporelle logarithmique de O(log n). Une compréhension approfondie des différentes classifications d'algorithmes aidera à sélectionner le meilleur algorithme pour une tâche spécifique et à améliorer le code pour améliorer les performances.

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!