Eléments d'Algorithmique

Comme on le voit dans la Table 1.1, l'algorithme fibo4 qui a la meilleure complexité est beaucoup plus rapide que les autres, et peut traiter des valeurs de n plus grandes. L'algorithme fibo1 prend très vite un temps trop élevée pour pouvoir être utilisée. Une autre limitation de fibo1 que l'on ne voit pas dans le tableau est la limite liée au nombre maximal de niveaux de récursivité autorisée dans un programme : en C cette valeur est souvent autour de quelques dizaines de milliers 2. On ne peut donc pas avoir plus que ce nombre d'appels récursifs imbriqués au sein d'un algorithme. Pour l'algorithme fibo2 la limite ne vient pas du temps de calcul, mais de la taille mémoire nécessaire : quand on essaye d'allouer un tableau de 228 entiers (soit 1Go de mémoire d'un seul bloc) le système d'exploitation n'arrive pas à satisfaire notre requête et n'alloue donc pas de mémoire, et puisque l'on ne teste pas si la mémoire a bien été allouée avant d'écrire dans notre tableau, un problème à l'allocation se traduit immédiatement par une erreur de segmentation mémoire à l'écriture.

Les dentitions récursives sont courantes en mathématiques. Nous avons vu au chapitre précédent l'exemple de la suite de Fibonacci, dé?nit par une relation de récurrence. En informatique, la notion de récursivité joue un rôle fondamental. Nous voyons dans ce chapitre la puissance de la récursivité au travers essentiellement de deux algorithmes de tri ayant les meilleures performances asymptotiques pour des algorithmes génériques. Nous terminons par une étude des solutions d'équations de récurrence entrant en jeu lors de l'analyse de complexité de tels algorithmes.