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 :

Rappels 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.

Afficher la correction 
def recherche_sequentielle(liste, nb):
    '''
    param liste: (list) une liste d'entiers
    param nb: (int) un entier
    '''
    i = 0
    while nb > liste[i] and i < len(liste)-1:
        i = i + 1
    if nb == liste[i]:
        return i
    else:
        return None

def recherche_dichotomique_v1(liste, nb):
    '''
    Version avec le return dans le while
    param liste: (list) une liste d'entiers
    param nb: (int) un entier
    '''
    a = 0
    b = len(liste)-1
    while a <= b:
        m = (a + b) // 2
        if nb == liste[m]:
            return m
        elif nb < liste[m]:
            b = m-1
        else:
            a = m + 1
    return None

def recherche_dichotomique_v2(liste, nb):
    '''
    Version avec le return en dehors du while
    param liste: (list) une liste d'entiers
    param nb: (int) un entier
    '''
    a = 0
    b = len(liste)-1
    m = (a + b) //2
    while b - a > 0 and nb != liste[m]:
        if nb < liste[m]:
            b = m-1
        else:
            a = m+1
        m = (a + b) //2
    if nb == liste[m]:
        return m
    else :
        return None
    
assert recherche_sequentielle([3], 1) == None
assert recherche_sequentielle([3], 5) == None
assert recherche_sequentielle([3], 3) == 0
assert recherche_sequentielle([3, 6, 9], 1) == None
assert recherche_sequentielle([3, 6, 9], 5) == None
assert recherche_sequentielle([3, 6, 9], 12) == None
assert recherche_sequentielle([3, 6, 9], 3) == 0
assert recherche_sequentielle([3, 6, 9], 6) == 1
assert recherche_sequentielle([3, 6, 9], 9) == 2

assert recherche_dichotomique_v1([3], 1) == None
assert recherche_dichotomique_v1([3], 5) == None
assert recherche_dichotomique_v1([3], 3) == 0
assert recherche_dichotomique_v1([3, 6, 9], 1) == None
assert recherche_dichotomique_v1([3, 6, 9], 5) == None
assert recherche_dichotomique_v1([3, 6, 9], 12) == None
assert recherche_dichotomique_v1([3, 6, 9], 3) == 0
assert recherche_dichotomique_v1([3, 6, 9], 6) == 1
assert recherche_dichotomique_v1([3, 6, 9], 9) == 2

assert recherche_dichotomique_v2([3], 1) == None
assert recherche_dichotomique_v2([3], 5) == None
assert recherche_dichotomique_v2([3], 3) == 0
assert recherche_dichotomique_v2([3, 6, 9], 1) == None
assert recherche_dichotomique_v2([3, 6, 9], 5) == None
assert recherche_dichotomique_v2([3, 6, 9], 12) == None
assert recherche_dichotomique_v2([3, 6, 9], 3) == 0
assert recherche_dichotomique_v2([3, 6, 9], 6) == 1
assert recherche_dichotomique_v2([3, 6, 9], 9) == 2

print('Les tests sont ok')

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.

2.a) Écrire une fonction qui prend un entier n en paramètre et renvoie le temps mis pour rechercher le nombre 10000 dans une liste triée de n nombres entiers compris entre 0 et 9999.

Remarque : on recherche volontairement le nombre 10000 pour avoir le pire cas.

2.b) Écrire le programme principal qui permet de visualiser l'évolution du coût de la recherche séquentielle.

2.c) Les hypothèses faites dans la question 1) sont-elles confirmées ?

3) Coût de l'algorithme dichotomique.

Reprendre les questions a, b et c précédentes en les appliquant à l'algorithme de recherche 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

5.a) Compléter le programme précédent avec une troisième courbe qui correspond à la recherche utilisant index().

5.b) Comment le coût de la méthode index() évolue-t-il en fonction de la taille des données ?

Remarque : le coût de la méthode index() est moins bon que celui de la recherche dichotomique car la méthode index() fonctionne aussi bien sur les listes triées que sur les listes non triées.

Afficher la correction 
from time import perf_counter
import matplotlib.pyplot as plt
from random import randint

def liste_triee_aleatoire(n):
    L = [randint(0, 9999) for _ in range(n)]
    L.sort()
    return L

def recherche_sequentielle(liste, nb):
    i = 0
    while nb > liste[i] and i < len(liste)-1:
        i = i + 1
    if nb == liste[i]:
        return i
    else:
        return None

def recherche_dichotomique(liste, nb):
    a = 0
    b = len(liste)-1
    while a <= b:
        m = (a + b) // 2
        if nb == liste[m]:
            return m
        elif nb < liste[m]:
            b = m-1
        else:
            a = m + 1
    return None

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

# ===== Fonctions de mesure des temps
NBREP = 20

def temps_recherche_sequentielle(n:int):
    """
    param n (int): taille de la liste dans laquelle la recherche sera faite
    return (float) : temps de la recherche en µs
    """
    # Création de la liste triee
    liste_triee = liste_triee_aleatoire(n)
    # Mesure du temps de recherche
    nb_repetitions = NBREP
    temps_final = float('inf')
    for _ in range(nb_repetitions):
        debut = perf_counter()
        # Début du code à mesurer
        recherche_sequentielle(liste_triee, 10000)
        # Fin du code à mesurer
        temps = perf_counter() - debut
        if temps < temps_final:
            temps_final = temps
    return temps_final*1000000

def temps_recherche_dichotomique(n:int):
    """
    param n (int): taille de la liste dans laquelle la recherche sera faite
    return (float) : temps de la recherche en µs
    """
    # Création de la liste triee
    liste_triee = liste_triee_aleatoire(n)
    # Mesure du temps de recherche
    nb_repetitions = NBREP
    temps_final = float('inf')
    for _ in range(nb_repetitions):
        debut = perf_counter()
        # Début du code à mesurer
        recherche_dichotomique(liste_triee, 10000)
        # Fin du code à mesurer
        temps = perf_counter() - debut
        if temps < temps_final:
            temps_final = temps
    return temps_final*1000000

def temps_recherche_index(n:int):
    """
    param n (int): taille de la liste dans laquelle la recherche sera faite
    return (float) : temps de la recherche en µs
    """
    # Création de la liste triee
    liste_triee = liste_triee_aleatoire(n)
    # Mesure du temps de recherche
    nb_repetitions = NBREP
    temps_final = float('inf')
    for _ in range(nb_repetitions):
        debut = perf_counter()
        # Début du code à mesurer
        recherche_index(liste_triee, 10000)
        # Fin du code à mesurer
        temps = perf_counter() - debut
        if temps < temps_final:
            temps_final = temps
    return temps_final*1000000


tab_n = [n for n in range(1, 1000, 20)]
tab_tps_sequentielle = [temps_recherche_sequentielle(n) for n in tab_n]
tab_tps_dichotomique = [temps_recherche_dichotomique(n) for n in tab_n]
tab_tps_index = [temps_recherche_index(n) for n in tab_n]
plt.plot(tab_n,tab_tps_sequentielle,'r. ', label='recherche sequentielle')
plt.plot(tab_n,tab_tps_dichotomique,'b. ', label='recherche dichotomique')
plt.plot(tab_n,tab_tps_index,'g. ', label='recherche index')
plt.xlabel('taille des données')
plt.ylabel('temps en µs')
plt.grid(True)
plt.legend()
plt.show()