Un petit test aura d’ailleurs lieu mardi 9 février dans l’esprit de ces questions préparées en distanciel.
On revient sur le travail sur la dichotomie donné début janvier.
Nathan (merci) code pour nous 🙂
Dichotomie et complexité, statistiques
Le sujet donné début janvier :
Les statistiques sur un tableau de trié de taille 42 donnent une moyenne de plus de 5 coups pour la recherche dichotomique. Pas étonnant, quand on sait que :
La complexité de la recherche dichotomique sur un tableau trié de taille 
Le code en cliquant ci-dessous…
from random import randint
def tab_alea_trie(n = 42, p = 100):
tab = [randint(0, p) for i in range(n)]
tab.sort()
return tab
#print(tab_alea_trie(12 , 5))
def rech_dicho(L, val):
c = 0
g = 0
d = len(L) - 1
while g <= d :
c += 1
m = (g + d) //2
if L[m] == val:
return m, c
elif L[m] > val:
d = m-1
else :
g = m+1
return -1, c
m = 0
for i in range(1000):
L = tab_alea_trie()
val = randint(0, 100)
m += rech_dicho(L, val)[1]
#print(L)
from math import log
print("Une moyenne de", m / 1000)
print("A comparer avec le log_2(42) :", log(42, 2))
