Cota superior asintótica | una forma de comparar las tasas de crecimiento de diferentes funciones

En matemáticas y ciencias de la computación, la notación Big O es una forma de comparar las tasas de crecimiento de diferentes funciones. A menudo se utiliza para comparar la eficiencia de diferentes algoritmos, lo que se hace calculando cuánta memoria se necesita y cuánto tiempo tarda en completarse.

La notación Big O se utiliza a menudo para identificar el grado de complejidad de un problema, también conocido como clase de complejidad del problema. El matemático Paul Bachmann (1837-1920) fue el primero en utilizar esta notación, en la segunda edición de su libro "Analytische Zahlentheorie", en 1896. Edmund Landau (1877-1938) popularizó la notación. Por esta razón, cuando se habla de los símbolos de Landau, se hace referencia a esta notación.

La notación Big O recibe su nombre del término "orden de la función", que se refiere al crecimiento de las funciones. La notación Big O se utiliza para encontrar el límite superior (la cantidad más alta posible) de la tasa de crecimiento de la función, lo que significa que calcula el tiempo más largo que tardará en convertir la entrada en la salida. Esto significa que un algoritmo puede agruparse según el tiempo que puede tardar en el peor de los casos, en el que se tomará siempre el camino más largo.

Más concretamente, dadas dos funciones positivas f ( x ) {\displaystyle f(x)} f(x) y g ( x ) {\displaystyle g(x)} $g(x)$ , decimos que f {\displaystyle f} está en el gran O de g {\displaystyle g} (escrito f ∈ O ( g ) {\displaystyle f\in O(g)} $f\in O(g)$ ) si para un tamaño suficientemente grande x {\displaystyle x} , f $f(x)\leq k\cdot g(x)$ para alguna constante k {\displaystyle k} .

Big O es una expresión que encuentra el tiempo de ejecución en el peor de los casos, mostrando la eficiencia de un algoritmo sin tener que ejecutar el programa en un ordenador. También es útil debido al hecho de que diferentes ordenadores pueden tener un hardware diferente, y por lo tanto necesitan diferentes cantidades de tiempo para completarlo. Dado que Big O siempre asume el peor caso, puede mostrar una medida consistente de la velocidad: independientemente del hardware, O ( 1 ) {\displaystyle O(1)} $O(1)$ siempre se va a completar más rápido que O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , porque tienen diferentes niveles de eficiencia.

Ejemplos

Todos los ejemplos siguientes utilizan código escrito en Python. Tenga en cuenta que esta no es una lista completa de tipos de Big O.

Constantemente

O ( 1 ) {\displaystyle O(1)} $O(1)$ siempre tarda la misma cantidad de tiempo independientemente de la entrada. Por ejemplo, tomemos una función que acepta un número entero (llamado x) y devuelve el doble de su valor:

def double(x): return x * 2 #Devuelve el valor de x por 2

Después de aceptar la entrada, esta función siempre tardará un paso en devolver una salida. Es constante porque siempre tomará la misma cantidad de tiempo, por lo que es O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Lineal

O ( n ) {\displaystyle O(n)} $O(n)$ aumenta según el tamaño de la entrada, representado por n {\displaystyle n} . Por ejemplo, para la siguiente función que acepta n y devuelve todos los números de 1 a n:

def count(n): i = 1 #Crea un contador llamado "i" con un valor de 1 mientras i <= n: #Mientras i es menor o igual que n print(i) #Imprime el valor de i i = i + 1 #Redefine i como "el valor de i + 1"

Si introdujéramos el valor de 5, entonces esto daría como resultado 1 , 2 , 3 , 4 , 5 {\diseño 1,2,3,4,5} $1,2,3,4,5$ , requiriendo 5 bucles para completarse. Del mismo modo, si introducimos 100, entonces saldría 1 , 2 $1,2,3...98,99,100$ , requiriendo 100 bucles para completarse. Si la entrada es n {\displaystyle n} , entonces el tiempo de ejecución del algoritmo es exactamente n {\displaystyle n} bucles cada vez, por lo tanto es O ( n ) {\displaystyle O(n)} $O(n)$ .

Factorial

O ( n ! ) {\Nsegún el estilo O(n!)} $O(n!)$ aumenta en cantidades factoriales, lo que significa que el tiempo que se tarda aumenta masivamente con la entrada. Por ejemplo, supongamos que deseamos visitar cinco ciudades del mundo y queremos ver todas las ordenaciones posibles (permutaciones). Un algoritmo que podríamos escribir utilizando la biblioteca itertools de Python es el siguiente:

import itertools #Importar la biblioteca itertools ciudades = ['Londres', 'París', 'Berlín', 'Ámsterdam', 'Roma'] #Una matriz de nuestras ciudades elegidas def permutations(cities): #Tomando una matriz de ciudades como entrada: for i in itertools.permutations(cities): #Por cada permutación de nuestros elementos (asignados a la variable "i") print(i) #Salida i

Este algoritmo calculará cada permutación única de nuestras ciudades y luego dará una salida. Los ejemplos de salida incluirán:

('Londres', 'París', 'Berlín', 'Ámsterdam', 'Roma') ('Londres', 'París', 'Berlín', 'Roma', 'Ámsterdam') ('Londres', 'París', 'Ámsterdam', 'Berlín', 'Roma') ... ('Roma', 'Ámsterdam', 'París', 'Berlín', 'Londres') ('Roma', 'Ámsterdam', 'Berlín', 'Londres', 'París') ('Roma', 'Ámsterdam', 'Berlín', 'París')

Aquí, nuestra lista de entrada tiene 5 elementos, y por cada selección nuestras opciones restantes disminuyen en 1. En otras palabras, nuestras 5 entradas eligen $5\times 4\times 3\times 2\times 1$ elementos (o 5 ! {\displaystyle 5!} $5!$ ). ¡Si nuestra entrada tiene n {\displaystyle n} ciudades, entonces el número de salidas es n ! {\displaystyle n!} $n!$ ; en general, suponiendo que pasamos por cada permutación, entonces necesitaremos O ( n ! ) {\displaystyle O(n!)} bucles $O(n!)$ para completarla.

Notación Little-o

Un concepto relacionado con la notación big-O es la notación little-o. Big-O se utiliza para decir que una función no crece más rápido que otra función, mientras que little-o se utiliza para decir que una función crece más lentamente que otra función. Si dos funciones crecen al mismo ritmo, se puede utilizar big-O pero no little-o. La diferencia entre big-O y little-o es similar a la diferencia entre ≤ {\displaystyle \leq } $\leq$ y < {\displaystyle <} $<$ .

Si f ( x ) {\displaystyle f(x)} crece más lentamente que g ( x ) {\displaystyle g(x)} $g(x)$ , entonces f ( x ) ∈ O ( $f(x)\in O(g(x))$ y f ( x ) ∈ o $f(x)\in o(g(x))$ .
Si f ( x ) {\displaystyle f(x)} crece al mismo ritmo que g ( x ) {\displaystyle g(x)} $g(x)$ , entonces f ( x ) ∈ O ( $f(x)\in O(g(x))$ pero f ( x ) ∉ o $f(x)\not \in o(g(x))$ .
Si f ( x ) {\displaystyle f(x)} crece a mayor velocidad que g ( x ) {\displaystyle g(x)} $g(x)$ , entonces f ( x ) ∉ O ( $f(x)\not \in O(g(x))$ y f ( x ) ∉ o $f(x)\not \in o(g(x))$ .

Preguntas y respuestas

P: ¿Qué es la notación Big O?

R: La notación Big O es una forma de comparar las tasas de crecimiento de diferentes funciones, a menudo utilizada para comparar la eficiencia de diferentes algoritmos mediante el cálculo de la cantidad de memoria y tiempo que se necesita para completarlos. También puede utilizarse para identificar la complejidad de un problema.

P: ¿Quién fue el primero en utilizar esta notación?

R: El matemático Paul Bachmann (1837-1920) fue el primero en utilizar esta notación en su libro "Analytische Zahlentheorie" en 1896.

P: ¿Qué significa la O grande?

R: Big O significa "orden de la función", que se refiere a la tasa de crecimiento de las funciones.

P: ¿Cómo se utiliza la Big O?

R: La notación Big O se utiliza para encontrar un límite superior (la cantidad más alta posible) en la tasa de crecimiento de la función, lo que significa que calcula el tiempo más largo que tardará en convertir una entrada en una salida. Esto significa que los algoritmos pueden agruparse por el tiempo que tardan en el peor de los casos, en el que se tomará siempre el camino más largo.

P: ¿Qué son los símbolos de Landau?

R: Los símbolos de Landau se refieren a la notación Big O, llamada así por Edmund Landau (1877-1938), que popularizó esta notación.

P: ¿Por qué es útil la Big O?

R: La Big O nos permite medir la velocidad sin tener que ejecutar los programas en los ordenadores, ya que siempre asume el peor de los casos, lo que la hace consistente independientemente de las diferencias de hardware entre los ordenadores. También muestra la eficiencia de un algoritmo sin tener que ejecutarlo realmente en un ordenador.