La conception d'algorithmes consiste à développer un processus mathématique pour résoudre un problème. L'analyse d'algorithme consiste à prédire les performances d'un algorithme. Les deux chapitres précédents ont présenté les structures de données classiques (listes, piles, files d'attente, files d'attente prioritaires, ensembles et cartes) et les ont appliquées pour résoudre des problèmes. Ce chapitre utilisera une variété d'exemples pour présenter des techniques algorithmiques courantes (programmation dynamique, diviser pour mieux régner et retour en arrière) permettant de développer des algorithmes efficaces.

La notation Big O obtient une fonction permettant de mesurer la complexité temporelle de l'algorithme en fonction de la taille d'entrée. Vous pouvez ignorer les constantes multiplicatives et les termes non dominants dans la fonction. Supposons que deux algorithmes effectuent la même tâche, telle qu'une recherche (recherche linéaire ou recherche binaire). Quel est le meilleur? Pour répondre à cette question, vous pouvez implémenter ces algorithmes et exécuter les programmes pour obtenir le temps d'exécution. Mais cette approche pose deux problèmes :

• Premièrement, de nombreuses tâches s'exécutent simultanément sur un ordinateur. Le temps d'exécution d'un programme particulier dépend de la charge du système.
• Deuxièmement, le temps d'exécution dépend d'une entrée spécifique. Prenons par exemple la recherche linéaire et la recherche binaire. Si un élément à rechercher se trouve être le premier de la liste, la recherche linéaire trouvera l'élément plus rapidement que la recherche binaire.

Il est très difficile de comparer des algorithmes en mesurant leur temps d’exécution. Pour surmonter ces problèmes, une approche théorique a été développée pour analyser les algorithmes indépendamment des ordinateurs et des entrées spécifiques. Cette approche se rapproche de l'effet d'un changement sur la taille de l'entrée. De cette façon, vous pouvez voir à quelle vitesse le temps d'exécution d'un algorithme augmente à mesure que la taille d'entrée augmente, vous pouvez donc comparer deux algorithmes en examinant leurs taux de croissance.

Envisagez la recherche linéaire. L'algorithme de recherche linéaire compare la clé avec les éléments du tableau de manière séquentielle jusqu'à ce que la clé soit trouvée ou que le tableau soit épuisé. Si la clé ne se trouve pas dans le tableau, elle nécessite des comparaisons n pour un tableau de taille n. Si la clé est dans le tableau, cela nécessite en moyenne n/2 comparaisons. Le temps d’exécution de l’algorithme est proportionnel à la taille du tableau. Si vous doublez la taille du tableau, vous vous attendez à ce que le nombre de comparaisons double. L'algorithme croît à un rythme linéaire. Le taux de croissance a un ordre de grandeur de n. Les informaticiens utilisent la notation Big O pour représenter « l’ordre de grandeur ». En utilisant cette notation, la complexité de l'algorithme de recherche linéaire est O(n), prononcé comme « ordre de n ». Nous appelons un algorithme avec une complexité temporelle de O(n) un algorithme linéaire, et il présente un taux de croissance linéaire.

Pour une même taille d’entrée, le temps d’exécution d’un algorithme peut varier en fonction de l’entrée. Une entrée qui entraîne le temps d'exécution le plus court est appelée entrée dans le meilleur des cas, et une entrée qui entraîne le temps d'exécution le plus long est appelée entrée dans le pire des cas. Analyse du meilleur cas et
L'analyse du pire des cas consiste à analyser les algorithmes pour leur entrée dans le meilleur des cas et leur entrée dans le pire des cas. L’analyse du meilleur et du pire des cas n’est pas représentative, mais l’analyse du pire des cas est très utile. Vous pouvez être assuré que l'algorithme ne sera jamais plus lent que dans le pire des cas.
Une analyse de cas moyen tente de déterminer la durée moyenne parmi toutes les entrées possibles de même taille. L'analyse de cas moyens est idéale, mais difficile à réaliser, car pour de nombreux problèmes, il est difficile de déterminer les probabilités et les distributions relatives des diverses instances d'entrée. L'analyse du pire des cas est plus facile à réaliser, c'est pourquoi l'analyse est généralement effectuée pour le pire des cas.

L'algorithme de recherche linéaire nécessite n comparaisons dans le pire des cas et n/2 comparaisons dans le cas moyen si vous recherchez presque toujours quelque chose dont vous savez qu'il figure dans la liste. En utilisant la notation Big O, les deux cas nécessitent un temps O(n). La constante multiplicative (1/2) peut être omise. L'analyse des algorithmes se concentre sur le taux de croissance. Les constantes multiplicatives n'ont aucun impact sur les taux de croissance. Le taux de croissance pour n/2 ou 100_n_ est le même que pour n, comme illustré dans le tableau ci-dessous, Taux de croissance. Par conséquent, O(n) = O(n/2) = O(100n).

Considérez l'algorithme permettant de trouver le nombre maximum dans un tableau de n éléments. Pour trouver le nombre maximum si n est 2, il faut une comparaison ; si n vaut 3, deux comparaisons. En général, il faut n - 1 comparaisons pour trouver le nombre maximum dans une liste de n éléments. L’analyse algorithmique est destinée aux entrées de grande taille. Si la taille d’entrée est petite, l’estimation de l’efficacité d’un algorithme n’a aucune importance. À mesure que n grandit, la partie n de l’expression n - 1 domine la complexité. La notation Big O vous permet d'ignorer la partie non dominante (par exemple, -1 dans le
expression n - 1) et mettez en surbrillance la partie importante (par exemple, n dans l'expression n - 1). Par conséquent, la complexité de cet algorithme est O(n).

La notation Big O estime le temps d'exécution d'un algorithme par rapport à la taille d'entrée. Si le temps n'est pas lié à la taille d'entrée, l'algorithme prend temps constant avec la notation O(1). Par exemple, une méthode qui récupère un élément à un index donné dans un tableau
prend un temps constant, car le temps n'augmente pas à mesure que la taille du tableau augmente.

Les sommations mathématiques suivantes sont souvent utiles dans l'analyse d'algorithmes :

La complexité temporelle est une mesure du temps d'exécution utilisant la notation Big-O. De même, vous pouvez également mesurer la la complexité de l'espace à l'aide de la notation Big-O. La La complexité spatiale mesure la quantité d'espace mémoire utilisée par un algorithme. La complexité spatiale de la plupart des algorithmes présentés dans le livre est O(n). c'est-à-dire qu'ils présentent un taux de croissance linéaire par rapport à la taille de l'entrée. Par exemple, la complexité spatiale pour la recherche linéaire est O(n).