def generer_liste(n:int) -> list :
l = []
for x in range(0, n):
a = randint(0, 1000)
l.append(a)
return sorted(l)
def recherche_naive_for(tab:list, valeur:int):
compteur = 0
for i in range(len(tab)):
compteur = compteur +1
if tab[i] == valeur :
return i, compteur
return -1, compteur
def dichotomie(tab:list, v:int) -> int:
debut = 0
fin = len(tab)-1
compteur = 0
while debut <= fin :
compteur = compteur +1
m = (debut + fin) // 2
if tab[m] == v:
return m, compteur
elif tab[m] < v :
debut = m+1
else :
fin = m-1
return -1, compteur
from recherche import generer_liste, recherche_naive_for, dichotomie
def essais_recherche_naive(taille_liste_max):
liste_essais = []
for i in range(1, taille_liste_max+1):
liste = generer_liste(i)
r = recherche_naive_for(liste, -1)[1]
liste_essais.append(r)
return liste_essais
def essais_recherche_dicho(taille_liste_max):
liste_essais = []
for i in range(1, taille_liste_max+1):
liste = generer_liste(i)
r = dichotomie(liste, -1)[1]
liste_essais.append(r)
return liste_essais
x = essais_recherche_naive(10)
print(x)
x = essais_recherche_dicho(10)
print(x)
from timeit import timeit
import pylab
def temps_recherche_naive(taille_liste, nb_repetitions):
imports = "from recherche import generer_liste," + \
"recherche_naive_for;" + \
"liste = generer_liste("+str(taille_liste)+")"
program = "recherche_naive_for(liste,-1)"
return timeit(setup=imports,
stmt=program,
number=nb_repetitions)
def temps_recherche_dicho(taille_liste, nb_repetitions):
imports = "from recherche import generer_liste," + \
"dichotomie;" + \
"liste = generer_liste("+str(taille_liste)+")"
program = "dichotomie(liste,-1)"
return timeit(setup=imports,
stmt=program,
number=nb_repetitions)