Notación Big O y análisis de algoritmos con ejemplos 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 tipo de fusión, ordenamiento de burbuja, tipo de inserción, y así. 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 encontrar el algoritmo más eficiente para resolver el problema en cuestión. 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.

¿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í:

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 desde 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, el product variable 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:

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 Jupyter, puede usar el %timeit literal seguido de la llamada a la función para encontrar el tiempo que tarda la función en ejecutarse:

%timeit fact(50)

Esto nos dará:

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 bucle.

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

%timeit fact2(50)

Esto resultará en:

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

El segundo algoritmo que involucra 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. 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 el Gran notación viene a jugar.

Análisis de algoritmos con notación Big-O

La notación Big-O significa 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 un particular instancia en la que ejecuta un algoritmo, como fact(50), sino más bien, qué tan bien lo hace escala dada una entrada creciente. ¡Esta es una métrica mucho mejor para evaluar que el tiempo concreto para una instancia concreta!

Por ejemplo, si hay un 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 is O (n²).

Para desarrollar la intuición:

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

At 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	Jefe)
Lineal	O (n)
Cuadrático	O (n²)
Cubic	O(n³)
Exponencial	O(2ⁿ)
Logarítmico	O (registro (n))
Log 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!

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 – JEFE)

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 Jefe) 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(result)

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

En el guión de arriba, independientemente del tamaño de entrada, o el número de elementos en la lista de entrada items, el algoritmo realiza solo 2 pasos:

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

Por lo tanto, la complejidad permanece constante.

Si dibuja un gráfico de líneas con el tamaño variable de la items entrada 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:

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 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 de la linear_algo() La función es lineal en el ejemplo anterior ya que el número de iteraciones del ciclo for será igual al tamaño de la entrada items matriz. Por ejemplo, si hay 4 artículos en el items list, 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:

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 resultará en:

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 el linear_algo():

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 entrada items lista. 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:

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 de arriba, puedes 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²):

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 complejidad logarítmica, como Búsqueda binaria. La búsqueda binaria busca un elemento en una matriz, marcando el medio de una matriz, y podando la mitad en la que no está el elemento. Lo vuelve a hacer para la mitad restante y continúa con los mismos pasos hasta encontrar el elemento. En cada paso, se mitades el número de elementos en la matriz.

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

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?

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:

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 realizan 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 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:

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

La complejidad de esta parte es O (5) ya que se están realizando cinco pasos constantes en esta pieza 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 de la siguiente pieza de código también es O (n):

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

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

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

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

Simplificando lo anterior obtenemos:

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 caso peor vs mejor

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 otra pieza de código:

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 None. 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 mejor complejidad del 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 tanto la complejidad del peor de los casos se convierte en O (n).

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

El return_squares() La función 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.