An谩lisis de algoritmos y notaci贸n Big O con ejemplos de Python

    Hay varias formas de resolver un problema utilizando un programa de computadora. Por ejemplo, hay varias formas de ordenar elementos en una matriz. Puedes usar fusionar ordenaci贸n, ordenamiento de burbuja, tipo de inserci贸n, etc. Todos estos algoritmos tienen sus pros y sus contras. Se puede pensar en un algoritmo como un procedimiento o f贸rmula para resolver un problema en particular. La pregunta es, 驴qu茅 algoritmo usar para resolver un problema espec铆fico cuando existen m煤ltiples soluciones al problema?

    El an谩lisis de algoritmos se refiere al an谩lisis de la complejidad de diferentes algoritmos y la b煤squeda del algoritmo m谩s eficiente para resolver el problema en cuesti贸n. Notaci贸n Big-O es una medida estad铆stica que se utiliza para describir la complejidad del algoritmo.

    En este art铆culo, revisaremos brevemente el an谩lisis de algoritmos y la notaci贸n Big-O. Veremos c贸mo se puede usar la notaci贸n Big-O para encontrar la complejidad del algoritmo con la ayuda de diferentes funciones de Python.

    驴Por qu茅 es importante el an谩lisis de algoritmos?

    Para comprender por qu茅 es importante el an谩lisis de algoritmos, tomaremos la ayuda de un ejemplo simple.

    Supongamos que un gerente asigna una tarea a dos de sus empleados para dise帽ar un algoritmo en Python que calcule el factorial de un n煤mero ingresado por el usuario.

    El algoritmo desarrollado por el primer empleado se ve as铆:

    def fact(n):
        product = 1
        for i in range(n):
            product = product * (i+1)
        return product
    
    print (fact(5))
    

    Observe que el algoritmo simplemente toma un n煤mero entero como argumento. Dentro de fact funcionar una variable llamada product se inicializa a 1. Un bucle se ejecuta de 1 a N y durante cada iteraci贸n, el valor en el product se multiplica por el n煤mero que itera el ciclo y el resultado se almacena en el product variable de nuevo. Despu茅s de que se ejecuta el ciclo, product La variable contendr谩 el factorial.

    Del mismo modo, el segundo empleado tambi茅n desarroll贸 un algoritmo que calcula el factorial de un n煤mero. El segundo empleado utiliz贸 una funci贸n recursiva para calcular el factorial de un programa como se muestra a continuaci贸n:

    def fact2(n):
        if n == 0:
            return 1
        else:
            return n * fact2(n-1)
    
    print (fact2(5))
    

    El administrador tiene que decidir qu茅 algoritmo utilizar. Para hacerlo, debe encontrar la complejidad del algoritmo. Una forma de hacerlo es encontrar el tiempo necesario para ejecutar los algoritmos.

    En el cuaderno de Jupyter, puede utilizar el %timeit literal seguido de la llamada a la funci贸n para encontrar el tiempo que tarda la funci贸n en ejecutarse. Mira el siguiente gui贸n:

    %timeit fact(50)
    

    Salida:

    9 碌s 卤 405 ns per loop (mean 卤 std. dev. of 7 runs, 100000 loops each)
    

    La salida dice que el algoritmo toma 9 microsegundos (m谩s / menos 45 nanosegundos) por ciclo.

    Del mismo modo, ejecute el siguiente script:

    %timeit fact2(50)
    

    Salida:

    15.7 碌s 卤 427 ns per loop (mean 卤 std. dev. of 7 runs, 100000 loops each)
    

    El segundo algoritmo que involucra la recursividad toma 15 microsegundos (m谩s / menos 427 nanosegundos).

    El tiempo de ejecuci贸n muestra que el primer algoritmo es m谩s r谩pido en comparaci贸n con el segundo algoritmo que involucra recursividad. Este ejemplo muestra la importancia del an谩lisis de algoritmos. En el caso de grandes insumos, la diferencia de rendimiento puede volverse m谩s significativa.

    Sin embargo, el tiempo de ejecuci贸n no es una buena m茅trica para medir la complejidad de un algoritmo, ya que depende del hardware. Se necesita una m茅trica de an谩lisis de complejidad m谩s objetiva para los algoritmos. Aqu铆 es donde entra en juego la notaci贸n Big O.

    An谩lisis de algoritmos con notaci贸n Big-O

    La notaci贸n Big-O es una m茅trica que se utiliza para encontrar la complejidad del algoritmo. B谩sicamente, la notaci贸n Big-O significa la relaci贸n entre la entrada al algoritmo y los pasos necesarios para ejecutar el algoritmo. Se indica con una gran “O” seguida de par茅ntesis de apertura y cierre. Dentro del par茅ntesis, la relaci贸n entre la entrada y los pasos dados por el algoritmo se presenta mediante “n”.

    Por ejemplo, si existe una relaci贸n lineal entre la entrada y el paso dado por el algoritmo para completar su ejecuci贸n, la notaci贸n Big-O utilizada ser谩 O (n). De manera similar, la notaci贸n Big-O para funciones cuadr谩ticas es O (n ^ 2)

    Las siguientes son algunas de las funciones de Big-O m谩s comunes:

    Nombre Big O

    ConstanteJefe)
    LinealEn)
    Cuadr谩ticoO (n ^ 2)
    C煤bicoO (n ^ 3)
    ExponencialO (2 ^ n)
    Logar铆tmicoO (registro (n))
    Log linealO (nlog (n))

    Para tener una idea de c贸mo se calcula la notaci贸n Big-O en, echemos un vistazo a algunos ejemplos de complejidad constante, lineal y cuadr谩tica.

    Complejidad constante (O (C))

    Se dice que la complejidad de un algoritmo es constante si los pasos necesarios para completar la ejecuci贸n de un algoritmo permanecen constantes, independientemente del n煤mero de entradas. La complejidad constante se denota por O (c) donde c puede ser cualquier n煤mero constante.

    Escribamos un algoritmo simple en Python que encuentre el cuadrado del primer elemento de la lista y luego lo imprima en la pantalla.

    def constant_algo(items):
        result = items[0] * items[0]
        print ()
    
    constant_algo([4, 5, 6, 8])
    

    En el script anterior, independientemente del tama帽o de entrada o del n煤mero de elementos en la lista de entrada items, el algoritmo realiza solo 2 pasos: encontrar el cuadrado del primer elemento e imprimir el resultado en la pantalla. Por tanto, la complejidad permanece constante.

    Si dibuja una gr谩fica de l铆nea con el tama帽o variable de la items ingrese en el eje xy el n煤mero de pasos en el eje y, obtendr谩 una l铆nea recta. Para visualizar esto, ejecute el siguiente script:

    import matplotlib.pyplot as plt
    import numpy as np
    
    x = [2, 4, 6, 8, 10, 12]
    
    y = [2, 2, 2, 2, 2, 2]
    
    plt.plot(x, y, 'b')
    plt.xlabel('Inputs')
    plt.ylabel('Steps')
    plt.title('Constant Complexity')
    plt.show()
    

    Salida:

    Complejidad lineal (O (n))

    Se dice que la complejidad de un algoritmo es lineal si los pasos necesarios para completar la ejecuci贸n de un algoritmo aumentan o disminuyen linealmente con el n煤mero de entradas. La complejidad lineal se denota por O (n).

    En este ejemplo, escribamos un programa simple que muestre todos los elementos de la lista en la consola:

    def linear_algo(items):
        for item in items:
            print(item)
    
    linear_algo([4, 5, 6, 8])
    

    La complejidad del linear_algo la funci贸n es lineal en el ejemplo anterior ya que el n煤mero de iteraciones del bucle for ser谩 igual al tama帽o de la entrada items formaci贸n. Por ejemplo, si hay 4 elementos en el items list, el bucle for se ejecutar谩 4 veces, y as铆 sucesivamente.

    El gr谩fico de complejidad lineal con entradas en el eje xy el n煤mero de pasos en el eje x es el siguiente:

    import matplotlib.pyplot as plt
    import numpy as np
    
    x = [2, 4, 6, 8, 10, 12]
    
    y = [2, 4, 6, 8, 10, 12]
    
    plt.plot(x, y, 'b')
    plt.xlabel('Inputs')
    plt.ylabel('Steps')
    plt.title('Linear Complexity')
    plt.show()
    

    Salida:

    Otro punto a tener en cuenta aqu铆 es que en el caso de una gran cantidad de entradas, las constantes se vuelven insignificantes. Por ejemplo, eche un vistazo al siguiente script:

    def linear_algo(items):
        for item in items:
            print(item)
    
        for item in items:
            print(item)
    
    linear_algo([4, 5, 6, 8])
    

    En el script anterior, hay dos bucles for que iteran sobre la entrada items lista. Por lo tanto, la complejidad del algoritmo se convierte en O (2n), sin embargo, en el caso de elementos infinitos en la lista de entrada, el doble del infinito sigue siendo igual al infinito, por lo que podemos ignorar la constante 2 (ya que en 煤ltima instancia es insignificante) y la complejidad del algoritmo sigue siendo O (n).

    Podemos verificar y visualizar a煤n m谩s esto trazando las entradas en el eje xy el n煤mero de pasos en el eje y como se muestra a continuaci贸n:

    import matplotlib.pyplot as plt
    import numpy as np
    
    x = [2, 4, 6, 8, 10, 12]
    
    y = [4, 8, 12, 16, 20, 24]
    
    plt.plot(x, y, 'b')
    plt.xlabel('Inputs')
    plt.ylabel('Steps')
    plt.title('Linear Complexity')
    plt.show()
    

    En el script anterior, puede ver claramente que y = 2n, sin embargo, la salida es lineal y se ve as铆:

    Complejidad cuadr谩tica (O (n ^ 2))

    Se dice que la complejidad de un algoritmo es cuadr谩tica cuando los pasos necesarios para ejecutar un algoritmo son una funci贸n cuadr谩tica del n煤mero de elementos en la entrada. La complejidad cuadr谩tica se denota como O (n ^ 2). Eche un vistazo al siguiente ejemplo para ver una funci贸n con complejidad cuadr谩tica:

    def quadratic_algo(items):
        for item in items:
            for item2 in items:
                print(item, ' ' ,item)
    
    quadratic_algo([4, 5, 6, 8])
    

    En el script anterior, puede ver que tenemos un bucle externo que recorre todos los elementos de la lista de entrada y luego un bucle interno anidado, que nuevamente recorre todos los elementos de la lista de entrada. El n煤mero total de pasos realizados es n * n, donde n es el n煤mero de elementos de la matriz de entrada.

    El siguiente gr谩fico traza el n煤mero de entradas frente a los pasos para un algoritmo con complejidad cuadr谩tica.

    Encontrar la complejidad de funciones complejas

    En los ejemplos anteriores, vimos que solo se estaba realizando una funci贸n en la entrada. 驴Qu茅 sucede si se realizan m煤ltiples funciones en la entrada? Eche un vistazo al siguiente ejemplo.

    def complex_algo(items):
    
        for i in range(5):
            print ("Python is awesome")
    
        for item in items:
            print(item)
    
        for item in items:
            print(item)
    
        print("Big O")
        print("Big O")
        print("Big O")
    
    complex_algo([4, 5, 6, 8])
    

    En el script anterior se est谩n realizando varias tareas, primero, se imprime una cadena 5 veces en la consola usando el print declaraci贸n. A continuaci贸n, imprimimos la lista de entrada dos veces en la pantalla y, finalmente, se imprime otra cadena tres veces en la consola. Para encontrar la complejidad de tal algoritmo, necesitamos dividir el c贸digo del algoritmo en partes e intentar encontrar la complejidad de las piezas individuales.

    Dividamos nuestro gui贸n en partes individuales. En la primera parte tenemos:

        for i in range(5):
            print ("Python is awesome")
    

    La complejidad de esta parte es O (5). Dado que se est谩n realizando cinco pasos constantes en este fragmento de c贸digo, independientemente de la entrada.

    A continuaci贸n, tenemos:

        for item in items:
            print(item)
    

    Sabemos que la complejidad del c贸digo anterior es O (n).

    De manera similar, la complejidad del siguiente c贸digo tambi茅n es O (n)

        for item in items:
            print(item)
    

    Finalmente, en el siguiente fragmento de c贸digo, se imprime una cadena tres veces, por lo que la complejidad es O (3)

        print("Big O")
        print("Big O")
        print("Big O")
    

    Para encontrar la complejidad general, simplemente tenemos que agregar estas complejidades individuales. Hag谩moslo:

    O(5) + O(n) + O(n) + O(3)
    

    Simplificando arriba obtenemos:

    O(8) + O(2n)
    

    Dijimos anteriormente que cuando la entrada (que tiene una longitud n en este caso) se vuelve extremadamente grande, las constantes se vuelven insignificantes, es decir, el doble o la mitad del infinito sigue siendo infinito. Por tanto, podemos ignorar las constantes. La complejidad final del algoritmo ser谩 O (n).

    Peor vs mejor complejidad de caso

    Por lo general, cuando alguien le pregunta sobre la complejidad del algoritmo, le pregunta sobre la complejidad del peor de los casos. Para comprender el mejor y el peor caso de la complejidad, consulte el siguiente script:

    def search_algo(num, items):
        for item in items:
            if item == num:
                return True
            else:
                return False
    nums = [2, 4, 6, 8, 10]
    
    print(search_algo(2, nums))
    

    En el script anterior, tenemos una funci贸n que toma un n煤mero y una lista de n煤meros como entrada. Devuelve verdadero si el n煤mero pasado se encuentra en la lista de n煤meros; de lo contrario, devuelve falso. Si busca 2 en la lista, se encontrar谩 en la primera comparaci贸n. Este es el mejor caso de complejidad del algoritmo en el que el elemento buscado se encuentra en el primer 铆ndice buscado. La mejor complejidad de caso, en este caso, es O (1). Por otro lado, si busca 10, se encontrar谩 en el 煤ltimo 铆ndice buscado. El algoritmo tendr谩 que buscar en todos los elementos de la lista, por lo que la complejidad del peor de los casos se convierte en O (n).

    Adem谩s de la complejidad del mejor y del peor caso, tambi茅n puede calcular la complejidad promedio de un algoritmo, que le dice “dada una entrada aleatoria, 驴cu谩l es la complejidad de tiempo esperada del algoritmo”?

    Complejidad espacial

    Adem谩s de la complejidad del tiempo, donde cuenta el n煤mero de pasos necesarios para completar la ejecuci贸n de un algoritmo, tambi茅n puede encontrar la complejidad del espacio, que se refiere al n煤mero de espacios que necesita asignar en el espacio de memoria durante la ejecuci贸n de un programa. .

    Eche un vistazo al siguiente ejemplo:

    def return_squares(n):
        square_list = []
        for num in n:
            square_list.append(num * num)
    
        return square_list
    
    nums = [2, 4, 6, 8, 10]
    print(return_squares(nums))
    

    En el script anterior, la funci贸n acepta una lista de n煤meros enteros y devuelve una lista con los correspondientes cuadrados de n煤meros enteros. El algoritmo tiene que asignar memoria para el mismo n煤mero de elementos que en la lista de entrada. Por lo tanto, la complejidad espacial del algoritmo se convierte en O (n).

    Conclusi贸n

    La notaci贸n Big-O es la m茅trica est谩ndar utilizada para medir la complejidad de un algoritmo. En este art铆culo, estudiamos qu茅 es la notaci贸n Big-O y c贸mo se puede utilizar para medir la complejidad de una variedad de algoritmos. Tambi茅n estudiamos diferentes tipos de funciones Big-O con la ayuda de diferentes ejemplos de Python. Finalmente, revisamos brevemente la complejidad del peor y mejor caso junto con la complejidad del espacio.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *