Le DM d’info. évoque la notion de fonction dont le temps de calcul est logarithmique en fonction des données qu’es aco ?
Voici un explication qui consiste a comparer deux exemples :
- Supposons qu’on ait une liste L de longueur n et qu’on veut savoir si un objet x est dans la liste alors on doit parcourir (au pire) toute la liste et tester si L[i]==x avec une boucle for de longueur n. Cet algorithme est de complexité au plus n si on compte seulement le nombres de tests d’égalité L[i]== x qu’on y fait.(Au plus n car on peut s’arrêter si le L[i]==x vaut True).
C’est un algorithme qu’on dit de complexité linéaire (le nombre (max.) de tests est une fonction linéaire de la longueur de la liste i.e. de la forme a.n ici a=1).
Voici maintenant un autre algorithme :
- Supposons qu’on ait des listes L disons dont les entrées sont des entiers qui sont triées dans l’ordre croissant. Par exemple L=[3,5,8,14,17,24,29,45,72]. Alors on peut imaginer un algorithme plus efficace pour tester si un entier x est dans L, qui marche pour toutes les listes triées. On compare x avec L[n//2]. S’il est égal c’est gagné. S’il est inférieur, on sait que x est dans la première partie de la liste et on remplace L par L[:n//2] i.e. la première partie de la liste. S’il est supérieur, on sait que x dans la deuxième partie de la liste et on remplace L par L[n//2+1 : ]. Et on recommence. Le nombre total de fois qu’il faudra essayer est inférieur ou égal à N où N est tel que 2^N < n ( à un près… en gros). Donc N< log_2(n). Ce programme est donc de complexité logarithmique : le nombre d’étapes est très inférieur à la longueur de la liste.
- Par exemple si on cherche si x=45 est dans la liste L précédente où n=9, au premier coup on compare 45 avec L[4]=17. On sait que 45 (s’il est là) est dans la seconde partie de la liste [24,29,45,72] qui est de longueur 4. On prend L=cette seconde partie. On compare alors 45 au nouveau L[2], or L[2]=45 et c’est fini en deux coups contre 8 avec la méthode du premier algorithme.
Nous programmerons un tel algorithme de recherche en faisant un jeu de devinettes en TP à la rentrée.
joffremp2 