Complejidad

La complejidad de los algoritmos es una medida que nos ayuda a entender cuánto tiempo o espacio (memoria) necesita un algoritmo para resolver un problema en función del tamaño de la entrada. La complejidad puede ser evaluada principalmente en términos de tiempo y espacio, y ayuda a comparar la eficiencia de diferentes algoritmos.

La notación Big-O es una forma de describir la complejidad de algoritmos en términos de cómo el tiempo o el espacio necesario para ejecutar un algoritmo crece con el tamaño de la entrada, (n). Es una herramienta esencial en el análisis de algoritmos, permitiendo comparar la eficiencia de diferentes algoritmos de forma abstracta e independiente de las características específicas de los sistemas en los que se ejecutan.

Complejidad temporal

La complejidad temporal mide el tiempo que lleva la ejecución de un algoritmo. La idea es ver cómo varía el tiempo de ejecución cuando el tamaño de la entrada cambia.

• O(1) - Complejidad constante: El tiempo de ejecución no cambia con el tamaño de la entrada. Por ejemplo, acceder a un elemento específico en un array.
• O(n) - Complejidad lineal: El tiempo de ejecución aumenta linealmente con el tamaño de la entrada. Por ejemplo, recorrer una lista de $n$ elementos.
• O(n²) - Complejidad cuadrática: El tiempo de ejecución aumenta proporcionalmente al cuadrado del tamaño de la entrada. Por ejemplo, el algoritmo de ordenación por inserción.
• O(log n) - Complejidad logarítmica: El tiempo de ejecución aumenta logarítmicamente con el tamaño de la entrada. Por ejemplo, la búsqueda binaria en listas ordenadas.
• O(2ⁿ) - Complejidad exponencial: El tiempo de ejecución aumenta exponencialmente con el tamaño de la entrada. Por ejemplo, la solución de fuerza bruta para el problema del subconjunto.

Complejidad espacial

La complejidad espacial mide la cantidad de memoria adicional que necesita un algoritmo para ejecutar. Aunque normalmente estamos más interesados en el tiempo de ejecución, el uso de memoria también es importante, especialmente para grandes conjuntos de datos.

Las funciones son idénticas a las de la complejidad temporal, pero aplicadas a espacio de memoria. Se enumeran dos a modo de ejemplo:

• O(1) - Espacio Constante: El algoritmo usa una cantidad fija de memoria, independientemente del tamaño de la entrada.
• O(n) - Espacio Lineal: El algoritmo usa memoria proporcional al tamaño de la entrada.