Mejor caso, peor caso y caso promedio de una búsqueda binaria

En este entregable se nos pide comparar el mejor caso, peor caso y caso promedio de una búsqueda binaria con el caso promedio de búsqueda en un conjunto implementado sobre una tabla dedispersión.

Lógicamente como resultado obtenemos 3 gráficas, donde comparamos en cada una los casos previamente expuestos.


GRÁFICAS



Gráfica A

Gráfica B



Gráfica C

Gráfica A: Casopromedio de búsq. en conjunto con tabla dispersión y mejor caso de búsq. binaria.
Gráfica B: Caso promedio de búsq. en conjunto con tabla dispersión y caso promedio de búsq. binaria.
Gráfica C:Caso promedio de búsq. en conjunto con tabla dispersión y peor caso de búsq. binaria.
CONCLUSIÓN

Como se puede ver en las gráficas, y teniendo en cuenta los conceptos estudiados en clase, podemosobservar que el coste de búsqueda en un conjunto implementado con tablas de dispersión es más eficiente que cualquiera de los tres casos de búsqueda binaria.

Así que como conclusión suponemosque el coste asintótico del caso promedio en la búsqueda en un conjunto implementado con tablas de dispersión es aproximadamente O(1).

Adjuntamos a continuación el código que hemos utilizado paramedir los tiempos del caso promedio en la búsqueda en un conjunto implementado con tablas de dispersión. El código de los casos en la búsqueda binaria se encuentran en el Entregable 1.


CÓDIGOfrom time import clock
from random import randint

f=open(r'C:\Users\Diego\Downloads\castellano.txt')
words=[line.strip() for line in f.readlines()]
f.close()

words.sort()

for kin range(5000,500001,5000):

words = words[:k]

a = set(words)

total = 0

list = []

for i in range(k//20):list.append(words[randint(0,len(words)-1)])

for elem in list:
t1 = clock()

aux = elem in a

t2 = clock()

t = t2-t1

total += t...