1 - Introducción a la complejidad algorítmica

En esta lección fijamos las bases de la complejidad algorítmica y de la notación Big-O. El objetivo es entender qué medimos, por qué lo hacemos y cómo impacta en el código que escribimos en Python.

1.1 ¿Qué es la complejidad de un algoritmo?

La complejidad describe cómo crece el consumo de recursos a medida que aumenta el tamaño de entrada n. Nos enfocamos en:

• Tiempo: cantidad de pasos elementales (comparaciones, asignaciones, accesos a memoria) que modelamos con O(f(n)).
• Espacio: memoria adicional usada, también modelada con O(f(n)) para distinguir si es constante, lineal o mayor.
• Costos ocultos: caché, alineación de datos, llamadas a funciones y uso de la pila en recursión.

La notación Big-O expresa la cota superior asintótica, es decir, el ritmo de crecimiento dominante a grandes n.

1.2 ¿Por qué necesitamos medirla?

Medir la complejidad permite tomar decisiones de diseño informadas:

• Comparar alternativas antes de escribir código definitivo.
• Predecir escalabilidad cuando los datos se multiplican.
• Negociar requisitos: elegir entre velocidad, memoria o simplicidad.
• Detectar cuellos de botella en prototipos y planificar optimizaciones.

Sin esta mirada, es fácil elegir una solución que funcione en casos pequeños pero colapse en producción.

1.3 Diferencia entre tiempo real y tiempo teórico

El análisis asintótico ignora constantes y asume un modelo ideal; el tiempo real depende de hardware y del entorno. Dos ejemplos:

• Un algoritmo O(n) con constantes grandes puede tardar más que uno O(n log n) para tamaños pequeños.
• La latencia de caché o del sistema operativo puede afectar mediciones, aunque el orden de complejidad sea el mismo.

Podemos medir en Python con un bucle simple y contadores de pasos:

def contar_pasadas(datos):
  pasos = 0
  for dato in datos:
    pasos += 1             # lectura del dato
    if dato % 2 == 0:
      pasos += 1           # comparación extra
  return pasos             # modelo teórico de pasos ejecutados

El código refleja un modelo de pasos. Para tiempo real usaríamos temporizadores del sistema, pero el orden de crecimiento sigue siendo O(n).

1.4 Modelos de cómputo

Elegir un modelo aclara qué operaciones cuentan como un paso:

• Modelo RAM clásico: cada acceso a memoria y operación aritmética cuesta 1 unidad; es el más usado para Big-O.
• Modelo con jerarquías: distingue caché y memoria principal; sirve para algoritmos que dependen de localidad.
• Modelo de E/S: cuenta lecturas y escrituras a disco; vital cuando los datos no caben en RAM.
• Modelo paralelo: considera hilos y sincronización; la complejidad incluye contención y divisiones de trabajo.

En este tutorial partimos del modelo RAM y señalamos cuando otros modelos cambian las conclusiones.

1.5 Importancia en Python y en estructuras de datos

Trabajar en Python permite centrarse en la lógica y evaluar el impacto de las estructuras:

• La gestión automática de memoria reduce errores, pero estructuras como listas y diccionarios tienen costos ocultos.
• Las estructuras de datos (listas, colas, pilas, árboles, tablas hash) tienen perfiles de complejidad distintos que impactan en cada operación.
• Optimizar la elección de estructura o el orden de operaciones suele rendir más que micro-ajustes.
• Medir y documentar Big-O facilita elegir la estructura adecuada y justificar cambios en revisiones de código.

Estas ideas guiarán los temas siguientes, donde profundizaremos en la notación, los tipos de complejidad temporal y espacial, y las formas de medirlos en práctica.