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 C.

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 C con un bucle simple y contadores de pasos:

long contar_pasadas(const int *datos, int n) {
  long pasos = 0;
  for (int i = 0; i < n; i++) {
    pasos++;               // lectura del dato
    if (datos[i] % 2 == 0) {
      pasos++;             // 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 C y en estructuras de datos

Trabajar en C expone los costos de tiempo y espacio sin abstracciones intermedias:

• El manejo manual de memoria con malloc y free permite ajustar el uso espacial pero introduce riesgos de fugas.
• Las estructuras de datos (arrays, listas, pilas, colas, árboles, tablas hash) tienen perfiles de complejidad distintos que impactan en cada operación.
• Optimizaciones como mover código común fuera de un bucle o reducir llamadas a funciones tienen impacto directo en el tiempo constante.
• 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.