3

Estoy intentando discutir la complejidad algoritmica del siguiente código:

def find_me(search_object, array):
    n = len(array)
    lower = 0
    upper = n - 1
    while lower <= upper:
        idx = (lower + upper) // 2
        if search_object < array[idx]:
            upper = idx - 1
        elif search_object > array[idx]:
            lower = idx + 1
        else:
            return idx
    raise ValueError("Value is not in the list")

En mi opinión, se trata de una búsqueda binaria y por lo tanto la complejidad algoritmica en este caso se representaria como O(n) = log (en base 2) de N, donde N es el numero de elementos de la lista. Así pues, en función de este número de elementos el algoritmo tardara más o menos. Sin embargo, normalmente cualquier función se puede expresar utilizando O grande haciendo uso del caso asintótico. Por el otro lado, existe O (theta) donde la función tiene que quedar limitada entre una cota superior y una cota inferior. El caso, es que no acabo de entender como encontrar esa cota inferior y cota superior (si es que se puede).

0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

Examina otras preguntas con la etiqueta o formula tu propia pregunta.