El análisis de algoritmos estudia cómo se comportan los algoritmos en términos de los recursos que consumen: principalmente tiempo (velocidad de ejecución) y espacio (memoria utilizada). El objetivo es poder comparar algoritmos de forma independiente a la máquina o al programador que los implemente.

Si dos programadores N y D implementan el mismo algoritmo de forma diferente, ambas implementaciones tendran el mismo orden de crecimiento. La diferencia entre ellas sera, a lo sumo, una constante multiplicativa:

Esto significa que dos implementaciones del mismo algoritmo solo difieren por un factor constante. Por eso, cuando hablamos de eficiencia, desligamos el algoritmo de su implementacion.

La complejidad temporal mide cuántas operaciones ejecuta un algoritmo en función del tamaño de la entrada n. Se calcula contando, línea por línea, cuántas veces se ejecuta cada instrucción y a que costo.

¿Qué son las operaciones elementales (OE)?

Son operaciones cuyo costo se considera proporcionalmente estable para el análisis. El modelo RAM (Random Access Machine) define cuáles son:

Estructura de un algoritmo (pseudocódigo)

Un algoritmo en pseudocódigo tiene la siguiente estructura:

# Variables globales (si las hay)
tipo NombreAlgoritmo (E tipo param1, E/S tipo param2) {
  # Área de variables locales
  tipo var1, var2
  # Cuerpo del algoritmo
  instrucciones...
  return valor
  # Si retorna algo: es FUNCIÓN
  # Si no retorna: es PROCEDIMIENTO
}

Determinar la función de eficiencia T(n) del siguiente algoritmo.

Pseudocódigo

int AlgoritmoSM (E int n) {
  int i, suma
  suma <- 0                    # 1 vez --> 1 * C1
  for i <- 1 to n do           # n+1 veces --> (n+1) * C2
    suma <- suma+i             # n veces --> n * C3
  endfor
  return suma                  # 1 vez --> 1 * C4
}

1 Seguimiento línea por línea

¿Por qué el for tiene 3 OE? Porque en cada pasada ocurren tres cosas: se evalúa la comparación i <= n, al terminar el cuerpo se incrementa i <- i+1 y la primera vez se hace la asignación i <- 1. Por eso la cabecera cuesta 3 OE por pasada.

2 Análisis tabulando (verificación empírica)

Corremos el algoritmo mentalmente para valores pequeños de n y contamos cuántas OE ocurren. Esto nos da una idea de cómo crece T(n) antes de calcularla formalmente.

Observa que cuando n aumenta en 1, T(n) siempre aumenta en 5. Eso confirma que el crecimiento es lineal: cada unidad adicional de n cuesta siempre lo mismo.

3 Tecnica de sumatorias para obtener T(n)

Este algoritmo no requiere sumatorias complejas porque cada línea se ejecuta un número fijo de veces. Simplemente sumamos los costos de todas las líneas:

Donde a = C2 + C3 y b = C1 + C2 + C4 son constantes positivas. El resultado es una función lineal en n.

Determinar la función de eficiencia de dos ciclos for anidados donde ambos van de 1 a n (límite fijo).

Pseudocódigo

AlgoritmoSM2 (E int A[n]) {
  x <- 1                       # 1 vez --> 1*1
  for i <- 1 to n do           # n+1 veces --> (n+1)*3
    for j <- 1 to n do         # n(n+1) veces --> n(n+1)*3
      x <- x + i               # n*n veces --> n^2 * 2
    endfor
  endfor
}

1 Seguimiento línea por línea

¿Por qué el for interno se ejecuta n*(n+1) veces? El for externo tiene n+1 pasadas de cabecera. Para cada una de esas pasadas, el for interno también tiene n+1 pasadas propias. Pero el cuerpo externo solo ocurre n veces, así que el for interno se lanza n veces, y cada lanzamiento tiene n+1 pasadas de cabecera. Total: n * (n+1).

2 Análisis tabulando (verificación empírica)

Contamos cuántas veces se ejecuta la línea más interna x <- x + i para cada n:

La diferencia entre filas crece: 21, 31, 41, 51... (aumenta en 10 cada vez). Diferencia de la diferencia = 10 = constante, función cuadrática confirmada.

3 Tecnica de sumatorias

Como ambos límites son fijos (no dependen del otro índice), no necesitamos sumatorias anidadas complejas. El cuerpo se ejecuta exactamente$n\cdot n=n^2$veces:

Y armamos T(n) sumando todos los costos:

Ahora el ciclo interno va de 1 a i (límite variable que depende del externo). Este es el caso más frecuente en el análisis de algoritmos de ordenamiento.

Pseudocódigo

AlgoritmoSM2 (E int A[n]) {
  x <- 1                       # 1 vez
  for i <- 1 to n do           # n+1 veces
    for j <- 1 to i do         # LÍMITE VARIABLE: depende de i
      x <- x + i
    endfor
  endfor
}

1 Seguimiento detallado (prueba de escritorio con n=5)

Rastreamos manualmente que valores toma j para cada valor de i, y contamos ejecuciones:

Observacion: Cuando i=1, j recorre 1 y 2 (la cabecera se ejecuta 2 veces = i+1, el cuerpo 1 vez = i). La cabecera siempre se ejecuta una vez mas que el cuerpo.

2 Análisis tabulando — verificar el patrón cuadrático

Las columnas del centro crecen como n(n+1)/2, una expresión cuadrática. Eso confirma que el algoritmo es cuadrático.

3 Resolucion formal con sumatorias

Sumatoria de la cabecera del for interno: el for j <- 1 to i tiene su cabecera ejecutandose i+1 veces (i pasadas que cumplen + 1 que falla).

Sumatoria del cuerpo x <- x + i:

Construccion de T(n): sumamos los costos de cada linea:

Este es el caso más rico: el ciclo interno es un while que duplica j, lo que produce un comportamiento logarítmico. Es el patrón que explica por qué algoritmos como búsqueda binaria o Merge Sort son tan eficientes.

Pseudocódigo

AlgoritmoXXX (E int n) {
  x <- 1                       # 1 vez --> 1*1
  for i <- 1 to n do           # n+1 veces --> (n+1)*3
    j <- 1                     # n veces --> n*1
    while (j <= n) do          # n*(log2(n)+2) veces --> n*(log2(n)+2)*1
      j <- j*2                 # n*(log2(n)+1) veces --> n*(log2(n)+1)*2
    endwhile
  endfor
}

1 Seguimiento detallado — ¿cuántas veces se ejecuta el while?

La clave es entender que hace j <- j*2. Cada vez que pasa el while, j se duplica:

El while termina cuando j > n, es decir cuando 2^k > n. ¿Cuántas veces se duplica antes de superar n?

1. +1 porque j empieza en 1 (= 2^0), no en 2 (= 2^1). La primera iteración no avanza hacia n, solo establece la posición inicial.
2. +1 porque la cabecera del while se evalúa una vez más al final: es la evaluación que falla la condición y causa la salida.

Por tanto, la cabecera del while se ejecuta${\log }_2(n)+2$veces por cada iteracion de i, y el cuerpo${\log }_2(n)+1$veces.

2 Análisis tabulando — verificar el crecimiento n*log(n)

Como el while tiene${\log }_2(n)+2$iteraciones por cada uno de los$n$valores de i:

Cada vez que n se duplica, el while agrega un paso mas y el for el doble de iteraciones. El resultado: el costo crece cómo$n\log (n)$, no cómo$n^2$.

3 Resolucion formal con sumatorias

El patrón clave: para una j que empieza en 1 y se duplica, el número de iteraciones del while es${\log }_2(n)+2$. Como i recorre$n$valores, la línea del while se ejecuta en total:

El cuerpo del while j <- j*2:

Construccion de T(n):

La complejidad espacial mide cuanta memoria adicional requiere un algoritmo. Se cuentan las variables locales, parametros y estructuras de datos utilizadas.