DAA - Analyse des algorithmes

Dans l'analyse théorique des algorithmes, il est courant d'estimer leur complexité au sens asymptotique, c'est-à-dire d'estimer la fonction de complexité pour une entrée arbitrairement grande. Le terme"analysis of algorithms" a été inventé par Donald Knuth.

L'analyse d'algorithme est une partie importante de la théorie de la complexité de calcul, qui fournit une estimation théorique des ressources requises d'un algorithme pour résoudre un problème de calcul spécifique. La plupart des algorithmes sont conçus pour fonctionner avec des entrées de longueur arbitraire. L'analyse des algorithmes consiste à déterminer la quantité de ressources temporelles et spatiales nécessaires pour l'exécuter.

Habituellement, l'efficacité ou le temps d'exécution d'un algorithme est indiqué comme une fonction reliant la longueur d'entrée au nombre d'étapes, appelée time complexity, ou volume de mémoire, appelé space complexity.

Le besoin d'analyse

Dans ce chapitre, nous discuterons de la nécessité d'analyser les algorithmes et de la manière de choisir un meilleur algorithme pour un problème particulier, car un problème de calcul peut être résolu par différents algorithmes.

En considérant un algorithme pour un problème spécifique, nous pouvons commencer à développer la reconnaissance de formes afin que des types de problèmes similaires puissent être résolus à l'aide de cet algorithme.

Les algorithmes sont souvent assez différents les uns des autres, bien que l'objectif de ces algorithmes soit le même. Par exemple, nous savons qu'un ensemble de nombres peut être trié à l'aide de différents algorithmes. Le nombre de comparaisons effectuées par un algorithme peut varier avec d'autres pour la même entrée. Par conséquent, la complexité temporelle de ces algorithmes peut différer. Dans le même temps, nous devons calculer l'espace mémoire requis par chaque algorithme.

L'analyse de l'algorithme est le processus d'analyse de la capacité de résolution de problèmes de l'algorithme en termes de temps et de taille requis (la taille de la mémoire pour le stockage pendant la mise en œuvre). Cependant, la principale préoccupation de l'analyse des algorithmes est le temps ou les performances requis. Généralement, nous effectuons les types d'analyses suivants -

  • Worst-case - Le nombre maximum de pas effectués sur n'importe quelle instance de taille a.

  • Best-case - Le nombre minimum de pas effectués sur toute instance de taille a.

  • Average case - Un nombre moyen de pas effectués sur n'importe quelle instance de taille a.

  • Amortized - Une séquence d'opérations appliquée à l'entrée de taille a moyenné au fil du temps.

Pour résoudre un problème, nous devons tenir compte du temps ainsi que de la complexité de l'espace car le programme peut s'exécuter sur un système où la mémoire est limitée mais l'espace adéquat est disponible ou peut être vice-versa. Dans ce contexte, si l'on comparebubble sort et merge sort. Le tri par bulles ne nécessite pas de mémoire supplémentaire, mais le tri par fusion nécessite de l'espace supplémentaire. Bien que la complexité temporelle du tri par bulle soit plus élevée que celle du tri par fusion, nous pouvons avoir besoin d'appliquer le tri par bulle si le programme doit s'exécuter dans un environnement où la mémoire est très limitée.