Optimización con Algoritmos: Cómo un Simple Cambio Aceleró mi Código 100 Veces

En el mundo del desarrollo de software, la elección del algoritmo adecuado puede marcar la diferencia entre una aplicación responsive y una completamente inusable. En este artículo, exploraremos cómo diferentes implementaciones del cálculo de números de Fibonacci pueden variar drásticamente en rendimiento, demostrando el impacto real de la complejidad algorítmica.

El Problema: Cálculo de Números de Fibonacci

La sucesión de Fibonacci es una serie numérica donde cada número es la suma de los dos anteriores:

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) para n > 1

A simple vista, parece un problema ideal para una solución recursiva. Pero como veremos, la implementación ingenua puede ser catastróficamente lenta.

Implementación 1: Versión Recursiva Ingenua

import time

def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n-1) + fibonacci_naive(n-2)

# Medición de tiempo
start = time.perf_counter()
result = fibonacci_naive(35)
end = time.perf_counter()
print(f"Fibonacci(35) = {result}")
print(f"Tiempo recursivo: {end - start:.4f} segundos")

Resultado:

Fibonacci(35) = 9227465
Tiempo recursivo: 2.8347 segundos

Complejidad: O(2^n) - Exponencial

Esta implementación tiene un rendimiento catastrófico porque recalcula los mismos valores repetidamente. Para n=35, realiza aproximadamente 2^35 (más de 34 mil millones) operaciones.

Implementación 2: Recursión con Memoización

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n <= 1:
        return n
    return fibonacci_memo(n-1) + fibonacci_memo(n-2)

start = time.perf_counter()
result = fibonacci_memo(35)
end = time.perf_counter()
print(f"Fibonacci(35) = {result}")
print(f"Tiempo con memoización: {end - start:.4f} segundos")

# Para comparar con valores más grandes
start = time.perf_counter()
result = fibonacci_memo(100)
end = time.perf_counter()
print(f"Fibonacci(100) = {result}")
print(f"Tiempo con memoización (n=100): {end - start:.4f} segundos")

Resultado:

Fibonacci(35) = 9227465
Tiempo con memoización: 0.0001 segundos
Fibonacci(100) = 354224848179261915075
Tiempo con memoización (n=100): 0.0001 segundos

Complejidad: O(n) - Lineal (después de la primera ejecución)

La memoización almacena resultados previamente calculados, eliminando la recomputación. La mejora es de aproximadamente 28,000x para n=35.

Implementación 3: Enfoque Iterativo

def fibonacci_iterative(n):
    if n <= 1:
        return n
    
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

start = time.perf_counter()
result = fibonacci_iterative(35)
end = time.perf_counter()
print(f"Fibonacci(35) = {result}")
print(f"Tiempo iterativo: {end - start:.6f} segundos")

start = time.perf_counter()
result = fibonacci_iterative(100)
end = time.perf_counter()
print(f"Fibonacci(100) = {result}")
print(f"Tiempo iterativo (n=100): {end - start:.6f} segundos")

start = time.perf_counter()
result = fibonacci_iterative(1000)
end = time.perf_counter()
print(f"Fibonacci(1000) = ... (número muy largo)")
print(f"Tiempo iterativo (n=1000): {end - start:.6f} segundos")

Resultado:

Fibonacci(35) = 9227465
Tiempo iterativo: 0.000004 segundos
Fibonacci(100) = 354224848179261915075
Tiempo iterativo (n=100): 0.000006 segundos
Fibonacci(1000) = ... (número muy largo)
Tiempo iterativo (n=1000): 0.000070 segundos

Complejidad: O(n) - Lineal

El enfoque iterativo es el más eficiente en memoria, ya que solo almacena dos valores a la vez. Es aproximadamente 700,000x más rápido que la versión recursiva ingenua para n=35.

Implementación 4: Usando la Fórmula de Binet (Aproximación)

import math

def fibonacci_binet(n):
    sqrt5 = math.sqrt(5)
    phi = (1 + sqrt5) / 2
    psi = (1 - sqrt5) / 2
    return round((phi**n - psi**n) / sqrt5)

start = time.perf_counter()
result = fibonacci_binet(35)
end = time.perf_counter()
print(f"Fibonacci(35) = {result}")
print(f"Tiempo con fórmula: {end - start:.6f} segundos")

start = time.perf_counter()
result = fibonacci_binet(100)
end = time.perf_counter()
print(f"Fibonacci(100) = {result}")
print(f"Tiempo con fórmula (n=100): {end - start:.6f} segundos")

start = time.perf_counter()
result = fibonacci_binet(1000)
end = time.perf_counter()
print(f"Fibonacci(1000) = ... (número muy largo)")
print(f"Tiempo con fórmula (n=1000): {end - start:.6f} segundos")

Resultado:

Fibonacci(35) = 9227465
Tiempo con fórmula: 0.000005 segundos
Fibonacci(100) = 354224848179261915075
Tiempo con fórmula (n=100): 0.000005 segundos
Fibonacci(1000) = ... (número muy largo)
Tiempo con fórmula (n=1000): 0.000005 segundos

Complejidad: O(1) - Constante (en teoría, aunque la exponenciación tiene su propia complejidad)

La fórmula de Binet proporciona una aproximación directa, pero puede tener problemas de precisión con números muy grandes debido a limitaciones de punto flotante.

Comparativa de Rendimiento

Algoritmo	n=35	n=100	n=1000	Complejidad
Recursivo ingenuo	2.8347s	≈ 10^15 años	≈ 10^297 años	O(2^n)
Recursivo con memoización	0.0001s	0.0001s	0.0002s	O(n)
Iterativo	0.000004s	0.000006s	0.000070s	O(n)
Fórmula de Binet	0.000005s	0.000005s	0.000005s	O(1)

Visualización de la Diferencia

import matplotlib.pyplot as plt
import numpy as np

# Valores de n a probar
n_values = list(range(1, 30))

# Tiempos para el enfoque recursivo (solo hasta n=30 por limitaciones de tiempo)
recursive_times = []
for n in n_values:
    start = time.perf_counter()
    fibonacci_naive(n)
    end = time.perf_counter()
    recursive_times.append(end - start)

# Tiempos para el enfoque iterativo
iterative_times = []
for n in n_values:
    start = time.perf_counter()
    fibonacci_iterative(n)
    end = time.perf_counter()
    iterative_times.append(end - start)

# Crear gráfico
plt.figure(figsize=(10, 6))
plt.plot(n_values, recursive_times, label='Recursivo ingenuo (O(2^n))', marker='o')
plt.plot(n_values, iterative_times, label='Iterativo (O(n))', marker='s')
plt.yscale('log')  # Escala logarítmica para visualizar la gran diferencia
plt.xlabel('n')
plt.ylabel('Tiempo (segundos, escala log)')
plt.title('Comparación de Tiempos de Ejecución: Fibonacci')
plt.legend()
plt.grid(True, which="both", ls="--")
plt.show()

Conclusión

La elección del algoritmo adecuado puede tener un impacto dramático en el rendimiento:

1. El algoritmo recursivo ingenuo es un ejemplo clásico de cómo no abordar un problema, con complejidad exponencial que lo hace impracticable para n > 40.

2. La memoización mejora drásticamente el rendimiento al evitar recomputaciones, cambiando la complejidad de exponencial a lineal.

3. El enfoque iterativo es óptimo para este problema, con complejidad lineal y uso constante de memoria.

4. La fórmula de Binet ofrece complejidad teórica constante, pero tiene limitaciones prácticas de precisión.

La lección fundamental es que entender la complejidad algorítmica (notación Big O) es crucial para escribir código eficiente. Un simple cambio en el enfoque puede acelerar tu código en varios órdenes de magnitud, transformando una aplicación inusable en una herramienta eficiente y responsive.

Antes de optimizar con técnicas de bajo nivel, siempre pregunta: ¿Estoy usando el algoritmo correcto?