Analyse de la complexité des algorithmes

vignette|Représentation d'une recherche linéaire (en violet) face à une recherche binaire (en vert). La complexité algorithmique de la seconde est logarithmique alors que celle de la première est linéaire. L'analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme. Celle-ci ne doit pas être confondue avec la théorie de la complexité, qui elle étudie la difficulté intrinsèque des problèmes, et ne se focalise pas sur un algorithme en particulier. Quand les scientifiques ont voulu énoncer formellement et rigoureusement ce qu'est l'efficacité d'un algorithme ou au contraire sa complexité, ils se sont rendu compte que la comparaison des algorithmes entre eux était nécessaire et que les outils pour le faire à l'époque étaient primitifs. Dans la préhistoire de l'informatique (les années 1950), la mesure publiée, si elle existait, était souvent dépendante du processeur utilisé, des temps d'accès à la mémoire vive et de masse, du langage de programmation et du compilateur utilisé. Une approche indépendante des facteurs matériels était donc nécessaire pour évaluer l'efficacité des algorithmes. Donald Knuth fut un des premiers à l'appliquer systématiquement dès les premiers volumes de sa série The Art of Computer Programming. Il complétait cette analyse de considérations propres à la théorie de l'information : celle-ci par exemple, combinée à la formule de Stirling, montre que, dans le pire des cas, il n'est pas possible d'effectuer, sur un ordinateur classique, un tri général (c'est-à-dire uniquement par comparaisons) de N éléments en un temps croissant avec N moins rapidement que N ln N. L'approche la plus classique est donc de calculer le temps de calcul dans le pire des cas. Il existe au moins trois alternatives à l'analyse de la complexité dans le pire des cas. La complexité en moyenne des algorithmes, à partir d'une répartition probabiliste des tailles de données, tente d'évaluer le temps moyen que l'on peut attendre de l'évaluation d'un algorithme sur une donnée d'une certaine taille.

Analyse de la complexité des algorithmes

Augmented Memory: Sample-Efficient Generative Molecular Design with Reinforcement Learning

Safe Schedule Verification for Urban Air Mobility Networks With Node Closures

Safe Schedule Verification for Urban Air Mobility Networks With Node Closures

Augmented Memory: Sample-Efficient Generative Molecular Design with Reinforcement Learning