6.5.4

#Daniel Bedialauneta
def rep(v): #n=len(v)
    d=dict() #1
    for i in v: #n
        if i in d: #Mirar si está en el diccionario tiene un coste fijo que no depende del tamaño del diccionario
            d[i]+=1
        else:
            d[i]=1
    lista=[] #1
    for i in d: #k
        if d[i]>1:
            lista.append(i)
    return lista #1

"""
Si decimos que k=numero de elementos diferentes
t(n)=1+n+1+k+1=n+k+3

Mejor caso: k=1 (todos los elementos iguales)
t(n)=n+4
t(n) está en O(n)

Peor caso: k=n (todos los elementos diferentes)
t(n)=2n+3
t(n) está en O(n) también

Aunque ambos pertenezcan al mismo O(g(n)) (en este caso O(n)), a efectos prácticos, en el peor caso se tarda el doble que en el mejor.
Es decir, t(n) pertenece a Theta(n)
"""

#Prueba de la última afirmación verde y de que crecen linealmente
import time
import random
longitud=10000000
v1=[0 for i in range(longitud)] #Mejor caso, todos repetidos
v2=[]
for i in range(longitud): #Peor caso, todos diferentes
    v2.append(i)

t1=time.process_time()
rep(v1)
t2=time.process_time()
rep(v2)
t3=time.process_time()

t_mejor_caso=t2-t1
t_peor_caso=t3-t1

print(longitud)
print("t_mejor_caso = {0:.40f}".format(t_mejor_caso))
print("t_peor_caso  = {0:.40f}".format(t_peor_caso))

"""
Para longitud=10.000 (diez mil)
t_mejor_caso = 0.0       (todos repetidos)
t_peor_caso  = 0.0156250 (todos diferentes)

longitud=100.000 (cien mil)
t_mejor_caso = 0.0156250
t_peor_caso  = 0.0312500

longitud=1.000.000 (un millón) Más significativo que los anteriores
t_mejor_caso = 0.1406250
t_peor_caso  = 0.2812500

longitud=10.000.000 (diez millones)
t_mejor_caso = 1.3906250
t_peor_caso  = 2.8906250

En 1.000.000 y en 10.000.000 (que son los más significativos) apreciamos
que el peor caso es doblemente más costoso que el mejor.
Además, entre estas dos longitudes observamos la linealidad de la función
"""