C7.6 : Complexité - TD 2
Algorithmes de recherche

Outils pour le TD

Dans ce TD on va réutiliser les outils de l'activité précédente :

• - Le module mathplolib pour tracer une courbe ;
• - La fonction mesure_temps() pour mesurer le temps d'exécution d'un code.

Rappel de quelques algorithmes de recherche

1) Algorithme séquentiel

A faire : Écrire une fonction recherche_sequentielle(liste, nb) qui prend une liste d'entiers triée et un entier en paramètres, et renvoie la position de l'entier dans la liste (ou None si le nombre n'est pas dans la liste). On n'utilisera pas les méthodes de l'objet list (la fonction len() est autorisée).

2) Algorithme dichotomique

A faire : Écrire la fonction recherche_dichotomique(liste, nb) identique à la précédente, mais qui utilise l'algorithme de recherche par dichotomie.

Comparaison de la complexité des deux algorithmes

Détermination du coût par analyse du code

1) Par une analyse de code, estimer la complexité de chacun des deux algorithmes dans le pire cas et préciser si elle est de type \(n^2,\) \(n\) ou \(log_2(n)\).

Visualisation graphique du coût

1) Écrire une fonction liste_triee_aleatoire(n) qui prend un nombre entier n en paramètre et renvoie une liste triée de n entiers aléatoires compris entre 0 et 9999.

2) Coût de l'algorithme séquentiel.

3) Coût de l'algorithme dichotomique.

4) Écrire un programme qui permet de visualiser, sur un même graphique, l'évolution du coût de la recherche d'un élément dans une liste par les deux méthodes.

5) Pour aller plus loin : comparaison avec la méthode index.

La fonction ci-dessous permet de faire une recherche d'une valeur dans une liste triée en utilisant la méthode index() des listes.

def recherche_index(liste, nb):
    try:
        return liste.index(nb)
    except(ValueError):
        return None