Quelques corrections en python (2)

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 :

2^5 = 32 < 42 < 64 = 2^6 donc \boxed{5 < \log_2(42) < 6.}

La complexité de la recherche dichotomique sur un tableau trié de taille N étant en \mathcal{O}\left(\log_2(N)\right).

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))

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.