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 :
donc
La complexité de la recherche dichotomique sur un tableau trié de taille étant en
.
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))