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 *