Complejidad y Rendimiento

Más allá de que funcione

Un programa que funciona no siempre es un buen programa. Cuando trabajamos con pocos datos, casi cualquier solución parece rápida. Pero, ¿qué pasa cuando la lista de usuarios pasa de cien a un millón? La eficiencia se vuelve crucial. Aquí es donde entra en juego el análisis de rendimiento.

No medimos la eficiencia en segundos, porque eso depende del hardware. En su lugar, medimos cómo escala un algoritmo, es decir, cómo crece su tiempo de ejecución o su uso de memoria a medida que aumenta el tamaño de la entrada. Para describir esta relación, usamos la notación Big O.

Notación Big O

noun

Una notación matemática que describe el comportamiento límite de una función cuando el argumento tiende hacia un valor particular o infinito. En informática, se usa para clasificar algoritmos según cómo responden a los cambios en el tamaño de la entrada.

La notación Big O se centra en el peor escenario posible. Si buscas un nombre en una agenda telefónica de un millón de personas, puede que lo encuentres en el primer intento (el mejor caso) o en el último (el peor caso). Los ingenieros de software se preparan para el peor caso para garantizar que el rendimiento de la aplicación siga siendo aceptable incluso bajo la máxima carga.

Big O ignora las constantes y los términos de menor orden. Un algoritmo que realiza $3n + 10$ operaciones y otro que realiza $n$ operaciones se consideran ambos $O(n)$ , porque a medida que $n$ se vuelve muy grande, el término $n$ domina el crecimiento.

Tiempo vs. Espacio

El rendimiento no se trata solo de velocidad. Hay dos recursos principales que debemos gestionar:

Complejidad temporal: ¿Cuánto tiempo más tarda un algoritmo a medida que crece la entrada?
Complejidad espacial: ¿Cuánta memoria más necesita un algoritmo a medida que crece la entrada?

A menudo, existe una compensación entre ambos. Un algoritmo puede ser increíblemente rápido pero consumir una enorme cantidad de memoria, o viceversa. La elección correcta depende de las limitaciones del problema: ¿estás trabajando en un dispositivo con poca memoria o necesitas una respuesta en tiempo real?

Este gráfico ilustra por qué es tan importante elegir el algoritmo correcto. Una solución $O(n^2)$ puede ser aceptable para 10 elementos, pero se vuelve insostenible para 10,000, mientras que una solución $O(n \log n)$ o $O(n)$ escala de manera mucho más manejable.

Bucles y complejidad

La estructura de tu código, especialmente los bucles, tiene un impacto directo en la complejidad. Un bucle simple que recorre una lista de n elementos generalmente tiene una complejidad temporal lineal, $O(n)$ .

# Complejidad: O(n) - Lineal
def find_max(numbers):
    max_val = numbers[0]
    # Este bucle se ejecuta n veces.
    for number in numbers:
        if number > max_val:
            max_val = number
    return max_val

Las cosas se complican con los bucles anidados. Si tienes un bucle dentro de otro, y ambos dependen del tamaño de la entrada n, la complejidad se vuelve cuadrática, $O(n^2)$ . Por cada elemento del bucle exterior, el bucle interior se ejecuta n veces.

# Complejidad: O(n^2) - Cuadrática
def find_duplicates(items):
    duplicates = []
    # El bucle exterior se ejecuta n veces.
    for i in range(len(items)):
        # El bucle interior también se ejecuta n veces.
        for j in range(len(items)):
            if i != j and items[i] == items[j]:
                if items[i] not in duplicates:
                    duplicates.append(items[i])
    return duplicates

Este segundo ejemplo es un caso clásico de una solución funcional pero no óptima. Si la lista items tiene 1000 elementos, los bucles anidados realizarán aproximadamente $1000 \times 1000 = 1,000,000$ de comparaciones. Existen formas mucho más eficientes de encontrar duplicados, por ejemplo, usando un conjunto (hash set) para lograr una complejidad de $O(n)$ .

Crecimientos comunes

Comprender las clases de complejidad comunes te ayuda a evaluar rápidamente la eficiencia de un algoritmo. Aquí hay una tabla de referencia.

Notación Big O	Nombre	Ejemplo
$O(1)$	Constante	Acceder a un elemento de un array por su índice.
$O(\log n)$	Logarítmico	Búsqueda binaria en una lista ordenada.
$O(n)$	Lineal	Encontrar un elemento en una lista no ordenada.
$O(n \log n)$	Log-lineal	Ordenación eficiente (Merge Sort, Quicksort).
$O(n^2)$	Cuadrático	Comparar cada elemento de una lista con todos los demás (bucles anidados).
$O(2^n)$	Exponencial	Resolver el problema del viajante mediante fuerza bruta.
$O(n!)$	Factorial	Generar todas las permutaciones de una lista.

Las complejidades por encima de $O(n \log n)$ suelen ser demasiado lentas para grandes conjuntos de datos y a menudo indican que existe un enfoque algorítmico mejor.

Es muy importante entender la notación Big O porque te ayuda a analizar la escalabilidad y eficiencia de los algoritmos.

Ahora que tienes una idea de cómo medir y clasificar el rendimiento, pongamos a prueba tus conocimientos.

Quiz Questions 1/5

¿Qué mide principalmente la notación Big O en el análisis de algoritmos?

Quiz Questions 2/5

Si un algoritmo tiene una complejidad temporal de $O(n^2)$ , ¿qué sucede con el tiempo de ejecución si el tamaño de la entrada se duplica?

Analizar la complejidad es una habilidad fundamental. Te permite tomar decisiones informadas sobre las estructuras de datos y los algoritmos, asegurando que tus aplicaciones no solo funcionen, sino que lo hagan de manera eficiente a cualquier escala.

Maestría en Lógica Algorítmica y Resolución de Problemas