La es una rama de las ciencias de la computación que estudia los recursos necesarios para resolver un problema mediante un algoritmo. Los dos recursos principales que se analizan son:

El objetivo es predecir cómo se comporta el algoritmo cuando la entrada crece, sin depender de detalles de hardware o lenguaje de programación.

La notación más común para describir la complejidad es la . Esta notación se enfoca en el y describe la del tiempo o espacio, ignorando constantes y términos de orden inferior.

Por ejemplo: Si un algoritmo realiza \(3n^2 + 5n + 100\) operaciones, decimos que es \(\boldsymbol{O(n^2)}\) porque el término dominante es \(n^2\) cuando \(n\) es grande.

El siguiente gráfico muestra cómo crecen diferentes funciones a medida que aumenta el tamaño de la entrada (\(n\)). Puede generarse con el código R que se incluye a continuación.

library(ggplot2)
n <- seq(1, 20, by = 0.1)
datos <- data.frame(
  n = rep(n, 6),
  operaciones = c(
    rep(1, length(n)),         # O(1)
    log2(n),                   # O(log n)
    n,                         # O(n)
    n * log2(n),               # O(n log n)
    n^2,                       # O(n^2)
    2^n                        # O(2^n)
  ),
  Complejidad = rep(c("O(1)","O(log n)","O(n)","O(n log n)","O(n^2)","O(2^n)"), each=length(n))
)
ggplot(datos, aes(x=n, y=operaciones, color=Complejidad)) +
  geom_line(size=1.2) +
  scale_y_continuous(limits=c(0,100), breaks=seq(0,100,20)) +
  labs(title="Crecimiento de las funciones de complejidad",
       x="Tamaño de entrada (n)", y="Operaciones (escala arbitraria)") +
  theme_minimal()
## Warning: Using `size` aesthetic for lines was deprecated in ggplot2 3.4.0.
## ℹ Please use `linewidth` instead.
## This warning is displayed once per session.
## Call ]8;;ide:run:lifecycle::last_lifecycle_warnings()lifecycle::last_lifecycle_warnings()]8;; to see where this warning was
## generated.
## Warning: Removed 234 rows containing missing values or values outside the scale range
## (`geom_line()`).

Observa cómo \(O(2^n)\) explota rápidamente, mientras que \(O(\log n)\) prácticamente no crece.

Vamos a comparar empíricamente un algoritmo \(\boldsymbol{O(n)}\) y uno \(\boldsymbol{O(n^2)}\). Simularemos la búsqueda lineal (\(O(n)\)) y una simulación de ordenamiento por burbuja simplificado (\(O(n^2)\)) midiendo el tiempo para distintos tamaños de entrada.

El código en R mide los tiempos y genera la gráfica. La Figura~\(\ref{fig:medicion}\) muestra el resultado.

# Funcion lineal: buscar el maximo (O(n))
buscar_max <- function(v) {
  maximo <- v[1]
  for (x in v) if (x > maximo) maximo <- x
  return(maximo)
}
# Funcion cuadratica: suma de todos los pares (O(n^2))
suma_pares <- function(v) {
  suma <- 0
  n <- length(v)
  for (i in 1:n) for (j in 1:n) suma <- suma + v[i] + v[j]
  return(suma)
}

tamanos <- c(10, 50, 100, 200, 400, 800)
tiempos <- data.frame(tamano=integer(), tiempo=numeric(), algoritmo=character())

set.seed(123)
for (n in tamanos) {
  vec <- runif(n)
  t_lin  <- system.time(buscar_max(vec))["elapsed"] * 1000
  t_cuad <- system.time(suma_pares(vec))["elapsed"] * 1000
  tiempos <- rbind(tiempos,
    data.frame(tamano=n, tiempo=t_lin,  algoritmo="O(n) busqueda maximo"),
    data.frame(tamano=n, tiempo=t_cuad, algoritmo="O(n^2) suma pares"))
}

ggplot(tiempos, aes(x=tamano, y=tiempo, color=algoritmo)) +
  geom_point(size=3) + geom_line(size=1) +
  labs(title="Comparacion experimental: O(n) vs O(n^2)",
       x="Tamano de entrada (n)", y="Tiempo (milisegundos)") +
  theme_minimal()

El gráfico muestra cómo el tiempo del algoritmo cuadrático crece mucho más rápido. Con \(n=800\), la diferencia ya es notable.

Además del tiempo, la memoria consumida puede ser crítica. La complejidad espacial se mide de forma similar:

En R, muchas funciones generan copias de los objetos (aunque existen optimizaciones como el copy-on-write). Por eso es importante tener en cuenta la complejidad espacial al manejar grandes volúmenes de datos.

Dadas dos matrices cuadradas \(A, B \in \mathbb{R}^{n \times n}\), el producto \(C = AB\) se define como \[\begin{equation} c_{ij} = \sum_{k=1}^n a_{ik} \, b_{kj}. \end{equation}\]

El cálculo directo con tres bucles anidados realiza \(n\) multiplicaciones y \(n-1\) sumas por cada entrada, resultando en \(n^3\) multiplicaciones y \(n^3 - n^2\) sumas. Por tanto, su complejidad temporal es \[\begin{equation} \boxed{O(n^3)}. \end{equation}\]

En R podemos medirlo empíricamente para confirmar que el tiempo crece cúbicamente con \(n\). El siguiente código genera la Figura~\(\ref{fig:tiempo-ingenuo}\).

multi_ingenua <- function(A, B) {
  n <- nrow(A)
  C <- matrix(0, n, n)
  for (i in 1:n)
    for (j in 1:n)
      for (k in 1:n)
        C[i,j] <- C[i,j] + A[i,k] * B[k,j]
  return(C)
}

tamanos <- c(10, 20, 30, 50, 80, 120)
tiempos <- sapply(tamanos, function(n) {
  A <- matrix(runif(n*n), n, n)
  B <- matrix(runif(n*n), n, n)
  system.time(multi_ingenua(A, B))["elapsed"]
})

datos <- data.frame(n = tamanos, tiempo = tiempos*1000)
ggplot(datos, aes(n, tiempo)) +
  geom_point(size=3) + geom_line() +
  geom_smooth(method = "lm", formula = y ~ I(x^3), se = FALSE,
              linetype="dashed", color="red") +
  labs(title = "Multiplicación ingenua (O(n^3))",
       x = "Tamaño n", y = "Tiempo (ms)") +
  theme_minimal()

Volker Strassen descubrió que se puede multiplicar matrices dividiendo cada una en cuatro bloques de tamaño \(n/2 \times n/2\) y usando solo 7 multiplicaciones de bloques en lugar de las 8 del enfoque ingenuo, a costa de sumas adicionales. Su fórmula recursiva conduce a la recurrencia \[\begin{equation} T(n) = 7\,T(n/2) + O(n^2). \end{equation}\]

Por el teorema maestro, esta recurrencia tiene solución \[\begin{equation} \boxed{T(n) = O(n^{\log_2 7}) \approx O(n^{2.807})}. \end{equation}\]

Strassen fue el primer algoritmo en romper la barrera cúbica y demostró que el exponente óptimo (llamado \(\omega\)) es menor que 3.

Tras Strassen, se inició una carrera para reducir aún más \(\omega\) mediante métodos aritméticos complejos:

Sin embargo, estos algoritmos rápidos tienen constantes enormes y solo son prácticos para matrices astronómicamente grandes. Por eso, en la práctica (y en R) se usa la multiplicación que aprovecha la memoria caché, o bibliotecas como y , con complejidad \(O(n^3)\) pero extremadamente optimizada.

La frontera teórica inferior es aún un misterio: se conjetura que \(\omega = 2\), pero no se ha probado.

Invertir una matriz cuadrada \(A\) de tamaño \(n \times n\) consiste en encontrar \(A^{-1}\) tal que \(AA^{-1} = I\). El método clásico es la (o factorización LU), que requiere \[\begin{equation} \boxed{O(n^3)} \end{equation}\] operaciones, igual que la multiplicación ingenua.

Un resultado fundamental de la teoría de complejidad algebraica (debido a Strassen y otros) es que . En otras palabras, si existe un algoritmo de multiplicación en tiempo \(O(n^\omega)\), entonces también existe un algoritmo de inversión en tiempo \(O(n^\omega)\).

La demostración se basa en la inversión por bloques: para una matriz \(2 \times 2\) por bloques, \[\begin{equation} A = \begin{pmatrix} B & C \\ D & E \end{pmatrix}, \quad A^{-1} = \begin{pmatrix} B^{-1} + B^{-1}C S^{-1} D B^{-1} & -B^{-1}C S^{-1} \\ -S^{-1} D B^{-1} & S^{-1} \end{pmatrix}, \end{equation}\] donde \(S = E - D B^{-1} C\) es el complemento de Schur. Calcular la inversa involucra dos inversiones de bloques más pequeños, varias multiplicaciones y sumas. Aplicando la recursión se obtiene una recurrencia donde la multiplicación es la operación dominante, heredando su exponente.

Por consiguiente, cualquier avance en la multiplicación matricial se traduce directamente en un avance para la inversión, la resolución de sistemas, el cálculo de determinantes y otras operaciones de álgebra lineal.

En R, la función calcula la inversa (o resuelve sistemas) usando rutinas de LAPACK, con complejidad \(O(n^3)\) pero extremadamente afinadas. Para matrices grandes, el tiempo de ejecución sigue aproximadamente una ley cúbica. El siguiente código genera la Figura~\(\ref{fig:tiempo-inv}\).

tiempos_inv <- sapply(tamanos, function(n) {
  A <- matrix(runif(n*n), n, n)
  system.time(solve(A))["elapsed"]
})
datos_inv <- data.frame(n = tamanos, tiempo = tiempos_inv*1000)
ggplot(datos_inv, aes(n, tiempo)) +
  geom_point(size=3) + geom_line() +
  geom_smooth(method = "lm", formula = y ~ I(x^3), se = FALSE,
              linetype="dashed", color="red") +
  labs(title = "Inversión con solve (O(n^3))",
       x = "Tamaño n", y = "Tiempo (ms)") +
  theme_minimal()