La idea principal del análisis asintótico de algoritmos es tener una medida de la eficiencia de los algoritmos que no dependan de las constantes específicas de la computadora y no requieran la implementación de algoritmos ni el tiempo que toman los programas para compararlos. Las notaciones asintóticas son herramientas matemáticas para representar la complejidad temporal de los algoritmos.

Veremos cómo difieren las notaciones $O$ y $o$. En resumen, ambas son notaciones asintóticas que especifican límites superiores para funciones y tiempos de ejecución de algoritmos. Sin embargo, la diferencia es que la $O$ puede ser asintóticamente ajustada, mientras que la $o$ asegura de que el límite superior no sea asintóticamente ajustado.

Análisis asintótico de algoritmos

El comportamiento asintótico de una función $f(n)$ se refiere al crecimiento de $f$ a medida que $n$ crece. Por lo general, ignoramos los valores pequeños de $n$ , ya que generalmente estamos interesados ​​en estimar qué tan lento será el programa en entradas grandes cuando $n \to \infty$. Una regla es que cuanto más lenta sea la tasa de crecimiento asintótico, mejor será el algoritmo. Aunque no siempre es cierto.

Por ejemplo, un algoritmo lineal $ f (n) = d n + k $ siempre es asintóticamente mejor que uno cuadrático, $ f (n) = cn ^ 2 + q $.

Notación $O$

La notación $O$ es una expresión matemática que describe la eficiencia de los algoritmos cuando sus argumentos tienden a un número muy grande. Se utiliza para describir la complejidad temporal y espacial de una función dada.

La complejidad del tiempo es un concepto que describe el tiempo de ejecución de una función: cuánto tarda la función en realizar su tarea. Los factores importantes a considerar para evaluar la complejidad del tiempo pueden ser la longitud de una matriz, la cantidad de comparaciones que se realizan o la cantidad de veces que se debe llamar a una función recursiva.

La complejidad del espacio describe la cantidad de memoria, o espacio, que se debe asignar para que se ejecute la función. Los factores importantes a considerar al evaluar la complejidad del espacio también pueden ser la longitud de una matriz, la cantidad de variables declaradas, la cantidad de copias de una estructura de datos, etc.

La notación $O$ se usa a menudo para describir el peor caso del caso esperado. Rara vez nos preocupamos por el mejor de los casos.

Por ejemplo, consideremos la complejidad del tiempo de clasificación de una matriz. ¡El mejor de los casos sería que cada matriz que ordenamos ya esté ordenada! De esa manera, no importa qué tan grande sea la matriz. Entonces, la complejidad del tiempo es independiente del tamaño de la matriz y se denota como O(1). Sin embargo, no es muy útil saberlo, ya que rara vez tendremos que desarrollar un algoritmo de ordenación si todas las matrices de entrada ya están ordenadas.

En seguida, definimos en términos matemáticos las definición de $O$. Para una función $g(n)$, $O(g(n))$ se define como: $$O(g(n)) = \{f(n):\text{Existen constantes positivas }c \text{ y } n_0 \text{ tales que } 0\leq f(n) \leq cg(n) \text{ para todo } n \geq n_0\}$$

Así que $O(g(n))$ es un conjunto de funciones para valores mayores a $n_0$ es menor o igual a $g(n)$. El comportamiento de la función con valores menores a $n_0$ no será importante ya que la notación $O$ analiza la función para valores grandes de $n$.

Notación $o$

La notación $o$ se utiliza para denotar un límite superior que no es asintóticamente estrecho. Se define formalmente como: $$o(g(n)) = \{f(n):\text{Para cualquier constante positiva }c \text{ existen constantes positivas } n_0 \text{ tales que } 0\leq f(n) \leq cg(n) \text{ para todo } n \geq n_0\}.$$

Tengamos en cuenta que en esta definición, el conjunto de funciones $f(n)$ es estrictamente más pequeño que $cg(n)$, lo que significa que la notación $o$ es un límite superior más fuerte que la notación $O$. En otras palabras, la notación $o$ no permite que la función $f(n)$ tenga la misma tasa de crecimiento que $g(n)$.

Intuitivamente, esto significa que a medida que $n \to \infty$, $f(n)$ se vuelve insignificante en comparación con $g(n)$, lo que define un límite matemático: $$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0.$$

Además, la desigualdad en la definición $o$ debería ser válida para cualquier constante $v$, mientras que para $O$ basta con encontrar alguna $c$ que satisfaga la desigualdad.

Si trazáramos una analogía entre la comparación asintótica de $f(n)$ y $g(n)$ y la comparación de los números reales $a$ y $b$ obtendríamos $f(n) = O(g(n)) \approx a \le b$ mientras que $f(n) = o(g(n)) \approx a < b$.

Intución de $O$

Consideremos la siguiente situación: vivo a 5 minutos del supermercado y empaco cada artículo en su propia bolsa.

Ahora, imaginemos que tengo una lista de compras particularmente grande y decido comprar todo lo que hay en esa lista en un solo día. ¿Cuál es la complejidad del tiempo y el espacio?

Sabiendo que vivo a 5 minutos del súper, traer mis compras en la bolsa siempre tomará 5 minutos, sin importar la cantidad de artículos que compre. Si compro un cartón de leche, me lleva 5 minutos traerlo de vuelta a casa. Si compro 10 cartones de leche, aún me tomará 5 minutos traerla de vuelta a casa. Por lo tanto, el tiempo que tardo es independiente de la cantidad de artículos que compre. Por lo tanto, la complejidad temporal se expresa como $O(1)$.

¿Qué pasa con la complejidad del espacio? En este caso, empacar cada artículo en su propia bolsa, lo que significa que una bolsa puede contener un solo artículo. Por lo tanto, a medida que compro más artículos, la cantidad de bolsas que necesitaré aumenta linealmente: 1 artículo requiere 1 bolsa, 3 artículos requieren 3 bolsas, 10 artículos requieren 10 bolsas, y así sucesivamente. Por lo tanto, la complejidad del espacio se expresa como $O(N)$, donde $N$ es el número de artículos que compro en el supermercado.

Otro ejemplo: Tenemos un algoritmo que es $O(n^2)$ y otro algoritmo que es $O(n)$. ¿Cómo interpretamo esto?

Una forma de verlo es obtener una estimación de la magnitud del problema ingresando el valor estimado de su conjunto de datos $n$. Si el tamaño de nuestros datos es de 3 millones, entonces habría alrededor de $3,000,000^2$ de operaciones para un algoritmo $O(n^2)$, que es alrededor de $9,000,000,000,000$, que es un montón.

El mismo conjunto de datos pero usando el algoritmo $O(n)$ tendría alrededor de $3,000,000$ operaciones, lo cual es mucho más manejable.

Recordemos que se pueden descartar términos y coeficientes de orden inferior cuando calculamos la $O$. Por lo tanto, el valor exacto no es importante aquí. Nos fijamos sólo en la magnitud de los problemas. Un algoritmo de un millón de operaciones es mucho mejor que un algoritmo de diez billones de operaciones.

Otra forma de ver esto es obtener la relación relativa entre dos tamaños de conjuntos de datos. Esto es útil si tiene puntos de referencia empíricos de cada uno de los algoritmos y desea extrapolar al ampliar.

Así que digamos que con 40000 clientes, el algoritmo de la lista tardó 30 segundos. Si duplicamos el tamaño de los datos, ¿cuánto tiempo tomaría? Así que ahora tenemos un conjunto de datos que tiene un tamaño de $2n$. Entonces el tiempo de ejecución sería alrededor $O((2n)^2) = O(4n^2)

Esto significa que duplicar el tamaño del conjunto de datos para un $O(n^2)$ aumentaría el tiempo de ejecución en un factor de 4. Esperamos que se ejecute durante unos 120 segundos.

Por otro lado, el algoritmo del conjunto es igual a $O(2n)$, lo que significa que duplicar el conjunto de datos solo duplica el tiempo de ejecución.