Notación Big O y análisis de algoritmos con ejemplos de Python

En esta guía, aprenda la intuición detrás y cómo realizar un análisis de complejidad algorítmica, incluido qué son Big-O, Big-Omega y Big-Theta, cómo calcular Big-O y comprender la notación, con ejemplos prácticos de Python.

Introducción

Por lo general, hay múltiples formas de resolver el problema usando un programa de computadora. Por ejemplo, hay varias formas de ordenar elementos en una matriz: puede usar ordenar por fusión, [ordenamiento de burbuja](/clasificacion-de-burbujas-en-python /), tipo de inserción, etc. Todos estos algoritmos tienen sus propios pros y contras y el trabajo del desarrollador es sopesarlos para poder elegir el mejor algoritmo para usar en cualquier caso de uso. En otras palabras, la pregunta principal es qué algoritmo usar para resolver un problema específico cuando existen múltiples soluciones al problema.

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. La notación Big-O es una medida estadística utilizada para describir la complejidad del algoritmo.

En esta guía, primero haremos una breve revisión del análisis de algoritmos y luego profundizaremos en 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.

{.icon aria-hidden=“true”}

Nota: La notación Big-O es una de las medidas utilizadas para la complejidad algorítmica. Algunos otros incluyen Big-Theta y Big-Omega. Big-Omega, Big-Theta y Big-O son intuitivamente iguales a la complejidad de tiempo mejor, promedio y peor que un algoritmo puede lograr. Por lo general, usamos Big-O como medida, en lugar de las otras dos, porque podemos garantizar que un algoritmo se ejecuta con una complejidad aceptable en su peor caso, funcionará en el promedio y en el mejor de los casos también. pero no al revés.

¿Por qué es importante el análisis de algoritmos? {#por qué es importante el análisis de algoritmos}

Para entender por qué es importante el análisis de algoritmos, tomaremos la ayuda de un ejemplo simple. Supongamos que un gerente le da 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í:

1
2
3
4
5
6
7
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 la función fact(), una variable llamada product se inicializa en 1. Un bucle se ejecuta de 1 a n y durante cada iteración, el valor en el producto se multiplica por el número que itera el bucle y el resultado se almacena de nuevo en la variable producto. Después de que se ejecute el ciclo, la variable producto contendrá el factorial.

De manera similar, el segundo empleado también desarrolló un algoritmo que calcula el factorial de un número. El segundo empleado usó una función recursiva para calcular el factorial del número n:

1
2
3
4
5
6
7
def fact2(n):
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print(fact2(5))

El gerente tiene que decidir qué algoritmo usar. Para hacerlo, han decidido elegir qué algoritmo se ejecuta más rápido. Una forma de hacerlo es encontrar el tiempo necesario para ejecutar el código en la misma entrada.

En el cuaderno de Jupyter, puede usar el literal %timeit seguido de la llamada a la función para encontrar el tiempo que tarda la función en ejecutarse:

1
%timeit fact(50)

Esto nos dará:

1
9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

El resultado dice que el algoritmo tarda 9 microsegundos (más/menos 45 nanosegundos) por bucle.

Del mismo modo, podemos calcular cuánto tiempo tarda en ejecutarse el segundo enfoque:

1
%timeit fact2(50)

Esto dará como resultado:

1
15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

El segundo algoritmo que implica la recursividad tarda 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. Cuando se trata de grandes entradas, 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 un algoritmo. 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 representa la relación entre la entrada al algoritmo y los pasos necesarios para ejecutar el algoritmo. Se denota con una "O" grande seguida de un paréntesis de apertura y cierre. Dentro del paréntesis, la relación entre la entrada y los pasos tomados por el algoritmo se presenta usando "n".

La conclusión clave es: Big-O no está interesado en una instancia particular en la que ejecuta un algoritmo, como fact(50), sino qué tan bien escala dada la entrada creciente. ¡Esta es una métrica mucho mejor para evaluar que el tiempo concreto para una instancia concreta!

Por ejemplo, si existe una relación lineal entre la entrada y el paso que toma 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²).

Para desarrollar la intuición:

  • O(n): en n=1, se da 1 paso. En n=10, se toman 10 pasos.
  • O(n²): en n=1, se da 1 paso. En n=10, se toman 100 pasos.

En n=1, ¡estos dos harían lo mismo! Esta es otra razón por la que observar la relación entre la entrada y el número de pasos para procesar esa entrada es mejor que solo evaluar funciones con alguna entrada concreta.

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


Nombre Gran O Constante O(c) O(n) lineal Cuadrático O(n²) Cúbico O(n³) Exponencial O(2ⁿ) Logarítmico O(log(n)) Registro lineal O (nlog (n))


Puedes visualizar estas funciones y compararlas:

En términos generales, cualquier cosa peor que lineal se considera una mala complejidad (es decir, ineficiente) y debe evitarse si es posible. La complejidad lineal está bien y generalmente es un mal necesario. Logarítmico es bueno. ¡Constante es increíble!

{.icon aria-hidden=“true”}

Nota: Dado que Big-O modela relaciones de entrada a pasos, por lo general eliminamos las constantes de las expresiones. O(2n) es el mismo tipo de relación que O(n): ambas son lineales, por lo que podemos denotar ambas como O(n). Las constantes no cambian la relación.

Para tener una idea de cómo se calcula un Big-O, 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:

1
2
3
4
5
def constant_algo(items):
    result = items[0] * items[0]
    print(result)

constant_algo([4, 5, 6, 8])

En el script anterior, independientemente del tamaño de entrada, o la cantidad de elementos en la lista de entrada “elementos”, el algoritmo realiza solo 2 pasos:

  1. Hallar el cuadrado del primer elemento
  2. Imprimiendo el resultado en la pantalla.

Por lo tanto, la complejidad permanece constante.

Si dibuja un gráfico de líneas con el tamaño variable de la entrada de “elementos” en el eje X y el número de pasos en el eje Y, obtendrá una línea recta. Vamos a crear un guión corto para ayudarnos a visualizar esto. No importa el número de entradas, el número de pasos ejecutados sigue siendo el mismo:

1
2
3
4
5
6
7
steps = []
def constant(n):
    return 1
    
for i in range(1, 100):
    steps.append(constant(i))
plt.plot(steps)

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 indica con O(n).

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

1
2
3
4
5
def linear_algo(items):
    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

La complejidad de la función linear_algo() es lineal en el ejemplo anterior, ya que el número de iteraciones del ciclo for será igual al tamaño de la matriz de elementos de entrada. Por ejemplo, si hay 4 elementos en la lista de “elementos”, el bucle for se ejecutará 4 veces.

Vamos a crear rápidamente una gráfica para el algoritmo de complejidad lineal con el número de entradas en el eje x y el número de pasos en el eje y:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
steps = []
def linear(n):
    return n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

Esto dará como resultado:

Una cosa importante a tener en cuenta es que con entradas grandes, las constantes tienden a perder valor. Esta es la razón por la que generalmente eliminamos las constantes de la notación Big-O, y una expresión como O (2n) generalmente se abrevia a O (n). Tanto O(2n) como O(n) son lineales: lo que importa es la relación lineal, no el valor concreto. Por ejemplo, modifiquemos linear_algo():

1
2
3
4
5
6
7
8
def linear_algo(items):
    for item in items:
        print(item)

    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

Hay dos bucles for que iteran sobre la lista de elementos de entrada. Por lo tanto, la complejidad del algoritmo se convierte en O(2n); sin embargo, en el caso de infinitos elementos en la lista de entrada, el doble de infinito sigue siendo igual a infinito. Podemos ignorar la constante 2 (ya que en última instancia es insignificante) y la complejidad del algoritmo sigue siendo O(n).

Visualicemos este nuevo algoritmo trazando las entradas en el eje X y el número de pasos en el eje Y:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
steps = []
def linear(n):
    return 2*n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

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²)

Se dice que la complejidad de un algoritmo es cuadrática cuando los pasos requeridos 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²):

1
2
3
4
5
6
def quadratic_algo(items):
    for item in items:
        for item2 in items:
            print(item, ' ' ,item2)

quadratic_algo([4, 5, 6, 8])

Tenemos un ciclo externo que itera a través de todos los elementos de la lista de entrada y luego un ciclo interno anidado, que nuevamente itera a través de 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 en la matriz de entrada.

El siguiente gráfico traza el número de entradas contra los pasos para un algoritmo con complejidad cuadrática:

Complejidad logarítmica - O(logn)

Algunos algoritmos logran una complejidad logarítmica, como Búsqueda binaria. La búsqueda binaria busca un elemento en una matriz, comprobando el centro de una matriz y eliminando la mitad en la que el elemento no está. Lo vuelve a hacer para la mitad restante y continúa con los mismos pasos hasta encontrar el elemento. En cada paso, reduce a la mitad el número de elementos de la matriz.

Esto requiere que la matriz sea ordenada, y que hagamos una suposición sobre los datos (como que está ordenado).

Cuando puede hacer suposiciones sobre los datos entrantes, puede tomar medidas que reduzcan la complejidad de un algoritmo. La complejidad logarítmica es deseable, ya que logra un buen rendimiento incluso con entradas muy escaladas.

¿Encontrar la complejidad de las funciones complejas? {#encontrar la complejidad de las funciones complejas}

En ejemplos anteriores, teníamos funciones bastante simples en la entrada. Sin embargo, ¿cómo calculamos el Big-O de las funciones que llaman (múltiples) otras funciones en la entrada?

Vamos a ver:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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 la secuencia de comandos anterior, se realizan varias tareas, primero, se imprime una cadena 5 veces en la consola usando la instrucción imprimir. 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 dicho algoritmo, necesitamos dividir el código del algoritmo en partes e intentar encontrar la complejidad de las piezas individuales. Marca la complejidad de cada pieza.

En la primera sección tenemos:

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

La complejidad de esta parte es O(5) ya que se realizan cinco pasos constantes en este fragmento de código independientemente de la entrada.

A continuación, tenemos:

1
2
for item in items:
    print(item)

Sabemos que la complejidad del código anterior es O(n). De manera similar, la complejidad de la siguiente pieza de código también es O(n):

1
2
for item in items:
    print(item)

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

1
2
3
print("Big O")
print("Big O")
print("Big O")

Para encontrar la complejidad general, simplemente tenemos que agregar estas complejidades individuales:

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

Simplificando lo anterior obtenemos:

1
O(8) + O(2n) = O(8+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 lo tanto, podemos ignorar las constantes. ¡La complejidad final del algoritmo será O(n)!

Complejidad del peor caso frente al mejor caso {#complejidad del caso peor frente al mejor caso}

Por lo general, cuando alguien le pregunta sobre la complejidad de un algoritmo, está interesado en la complejidad del peor de los casos (Big-O). A veces, también pueden estar interesados ​​en la complejidad del mejor de los casos (Big-Omega).

Para comprender la relación entre estos, echemos un vistazo a otro fragmento de código:

1
2
3
4
5
6
7
8
9
def search_algo(num, items):
    for item in items:
        if item == num:
            return True
        else:
            pass
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 Ninguno. Si busca 2 en la lista, se encontrará en la primera comparación. Esta es la complejidad del mejor de los casos del algoritmo en el que el elemento buscado se encuentra en el primer índice buscado. La complejidad del mejor 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).

{.icon aria-hidden=“true”}

Nota: La complejidad en el peor de los casos sigue siendo la misma incluso si intenta encontrar un elemento inexistente en una lista: se necesitan n pasos para verificar que no existe tal elemento en una lista. Por lo tanto, la complejidad del peor de los casos sigue siendo O(n).

Además de la complejidad del mejor y el peor de los casos, también puede calcular la complejidad promedio (Big-Theta) 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 de tiempo, donde cuenta la cantidad de pasos necesarios para completar la ejecución de un algoritmo, también puede encontrar la complejidad de espacio que se refiere a la cantidad de espacio que necesita asignar en la memoria durante la ejecución de un programa.

Echa un vistazo al siguiente ejemplo:

1
2
3
4
5
6
7
8
9
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))

La función return_squares() acepta una lista de enteros y devuelve una lista con los cuadrados correspondientes. 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 esta guía, estudiamos qué es la notación Big-O y cómo se puede usar 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 el peor y el mejor caso de complejidad junto con la complejidad del espacio.