Tema 1: Análisis de algoritmos

Qué se analiza

Para un mismo problema suele haber varios programas, y se pueden comparar por muchos criterios (legibilidad, interfaz, memoria, consumo…). En este tema el criterio es la eficiencia: el mejor aprovechamiento de los recursos.

Se estudian los algoritmos (los métodos), no los programas (sus implementaciones en un lenguaje concreto).

Hay dos recursos:

Complejidad espacial: memoria que consume (memory-bound).
Complejidad temporal: tiempo que tarda (compute-bound).

Suelen ser objetivos contrapuestos: a menudo se gana tiempo gastando más memoria, y hay que buscar un compromiso. El tema se centra en la temporal, pero todo vale igual para la espacial.

Análisis teórico y experimental

	Análisis teórico (a priori)	Análisis experimental (a posteriori)
Qué hace	Obtiene una expresión matemática del coste en función de los parámetros	Ejecuta casos de prueba y mide tiempos
Depende de	Solo del algoritmo	Máquina, lenguaje, compilador y datos concretos
Sirve para	Generalizar	Caracterizar el programa en sus condiciones de uso

Extrapolar medidas es peligroso

Generalizar a partir de medidas suele llevar a errores graves. En las diapositivas, con tallas pequeñas parece que el tiempo es constante y que un algoritmo es el mejor; midiendo hasta 4096 la realidad es muy distinta.

El análisis teórico interesa porque permite predecir el coste sin implementar el algoritmo y se puede usar ya en la fase de diseño.

Talla, paso y coste temporal

Talla del problema: valor o valores de la entrada que miden su tamaño.

Entrada	Talla
Vector	Número de elementos
Matriz	Dimensiones
Número	El propio número

Paso: fragmento de código cuyo tiempo no depende de la talla y está acotado por una constante. Es lo que se suele llamar operación elemental: operaciones aritméticas y lógicas, comparaciones, accesos a variables o a elementos de vectores, asignaciones, lecturas, retornos…

Como cada paso tarda un tiempo acotado en cualquier máquina, se supone que todos tardan lo mismo, y el coste se mide en pasos, no en segundos.

Coste temporal de un algoritmo: función que da el número de pasos que necesita el algoritmo para cada talla posible.

Principio de invarianza: dos implementaciones del mismo algoritmo solo se diferencian en una constante multiplicativa. Si $t_1(n)$ y $t_2(n)$ son sus tiempos:

\exists\, c \in \mathbb{R}^+,\ \exists\, n_0 \in \mathbb{N} : \quad t_1(n) \le c\, t_2(n) \quad \forall n \ge n_0

Un factor 10 o 100 importa poco frente a una diferencia en cómo crece el coste con la talla: para tallas grandes, eso es lo que decide. Por eso el algoritmo es más importante que el programa.

Ejemplo: tres formas de calcular $n^2$

Funcion Solucion1 (n: entero) retorna (m: entero)
  m = n*n;                      // 2 pasos
  retorna m                     // 1 paso
ffuncion

Funcion Solucion2 (n: entero) retorna (m: entero)
  m = 0;                        // 1 paso
  para i = 1 hasta n hacer      // 2n + 2 pasos
    m = m + n;                  // 2 pasos, n veces
  fpara
  retorna m                     // 1 paso
ffuncion

Funcion Solucion3 (n: entero) retorna (m: entero)
  m = 0;                        // 1 paso
  para i = 1 hasta n hacer      // 2n + 2 pasos
    para j = 1 hasta n hacer    // 2n + 2 pasos, n veces
      m++;                      // 1 paso, n² veces
    fpara
  fpara
  retorna m                     // 1 paso
ffuncion

Un bucle para i = 1 hasta n cuesta $2n + 2$ pasos: 1 asignación, $n+1$ comparaciones y $n$ incrementos.

Solución	Pasos
1	$3$ (constante)
2	$1 + (2n+2) + 2n + 1 = 4n + 4$
3	$1 + (2n+2) + (2n+2)n + n^2 + 1 = 3n^2 + 4n + 4$

Aunque se dé un coste distinto a cada operación (en las diapositivas, producto 30 µs, suma 20 µs y el resto 1 µs), las gráficas tienen la misma forma: la solución 1 acaba siendo siempre la mejor. Un método de tiempo constante acaba ganando a uno lineal, y uno lineal a uno cuadrático. Se dice que la solución 1 es asintóticamente más eficiente que las otras dos, y la 2 que la 3.

Instancias: mejor, peor y caso promedio

El coste no siempre depende solo de la talla.

Instancia: factor con el que varía el coste para una talla fija. Es un caso particular del problema que hace que el algoritmo se comporte de una forma u otra.

Búsqueda secuencial

función Secuencial(A[1..n]: vector de enteros; x: entero) retorna (i: entero)
  i = 1;
  mientras (i ≤ n y A[i] ≠ x) hacer
    i = i + 1;
  fmientras
  retorna i
ffunción

Con $n$ fijo, $x$ puede estar en la posición 1, en la 2…, en la $n$ , o no estar. Cada caso es una instancia distinta y cuesta distinto.

Mejor caso: instancias que, para cada talla, se resuelven más rápido. Aquí, $x$ en la primera posición: coste constante.
Peor caso: instancias que, para cada talla, necesitan más pasos. Aquí, $x$ no está: coste lineal.
Caso promedio: necesita conocer la probabilidad de cada instancia.

¿Cuál da más información? Depende. El promedio parece el más interesante, pero en algunas aplicaciones importa más el peor caso (un algoritmo razonable de media puede ser prohibitivo en el peor).

En la asignatura se estudian el mejor y el peor caso porque:

Son fáciles de analizar; el promedio exige conocer la distribución de probabilidades y matemáticas más avanzadas.
El promedio siempre está entre los dos, así que ya dan información sobre él.

Error típico: confundir instancia con talla

Una instancia cambia el coste sin cambiar la talla. Que el algoritmo haga algo distinto cuando $n = 0$ no es una instancia: $n = 0$ es un valor de la talla.

Notación asintótica

Estudia el comportamiento para tallas suficientemente grandes, sin fijarse en lo que pasa con tallas pequeñas y olvidando las constantes. Sean $f, g : \mathbb{N} \to \mathbb{R}^+$ , con $f(n)$ el coste del algoritmo.

$O$ (o grande): cota superior

f(n) \in O(g(n)) \iff \exists\, c \in \mathbb{R}^+,\ \exists\, n_0 \in \mathbb{N} : \quad f(n) \le c\, g(n) \quad \forall n \ge n_0

$g$ domina asintóticamente a $f$ : a partir de $n_0$ , $f$ nunca supera a un múltiplo de $g$ . $O(g(n))$ es el conjunto de funciones acotadas superiormente por $g$ .

Ejemplos

$3n + 2 \in O(n)$ : con $c = 4$ , $3n + 2 \le 4n$ para todo $n \ge 2$ .
$10n^2 + 4n + 2 \notin O(n)$ : no hay $c$ ni $n_0$ que valgan, porque $n^2$ acaba superando a cualquier $cn$ .

$\Omega$ (omega): cota inferior

f(n) \in \Omega(g(n)) \iff \exists\, c \in \mathbb{R}^+,\ \exists\, n_0 \in \mathbb{N} : \quad f(n) \ge c\, g(n) \quad \forall n \ge n_0

$g$ es dominada por $f$ : hay un múltiplo de $g$ que $f$ nunca baja.

Ejemplos

$10n^2 + 4n + 2 \in \Omega(n^2)$ : con $c = 10$ , $10n^2 + 4n + 2 \ge 10n^2$ para todo $n \ge 0$ .
$10n^2 + 4n + 2 \in \Omega(n)$ : con $c = 1$ , $10n^2 + 4n + 2 \ge n$ para todo $n \ge 0$ .

$\theta$ (theta): orden exacto

f(n) \in \theta(g(n)) \iff \exists\, c_1, c_2 \in \mathbb{R}^+,\ \exists\, n_0 \in \mathbb{N} : \quad c_1\, g(n) \le f(n) \le c_2\, g(n) \quad \forall n \ge n_0

Es decir, $f(n) \in \theta(g(n)) \iff f(n) \in O(g(n)) \land f(n) \in \Omega(g(n))$ : $f$ domina y es dominada por $g$ .

Jerarquía de órdenes

O(1) \subset O(\log n) \subset O(\sqrt{n}) \subset O(n) \subset O(n \log n) \subset O(n^2) \subset O(n^3) \subset O(2^n) \subset O(n^n)

Con $\Omega$ las inclusiones van al revés: $\Omega(n^n) \subset \Omega(2^n) \subset \dots \subset \Omega(\log n) \subset \Omega(1)$ .

Así, $3n + 2$ está en $O(n)$ , pero también en $O(n^2)$ y en $O(2^n)$ . Siempre se da la cota más ajustada.

Tipo	Orden
Constante	$O(1)$
Logarítmica (sublineal)	$O(\log n)$ , $O(\sqrt{n})$
Lineal	$O(n)$
Superlineal	$O(n \log n)$
Polinómica: cuadrática, cúbica	$O(n^2)$ , $O(n^3)$
Exponencial	$O(2^n)$ , $O(n^n)$

Propiedades de las cotas

Todas valen igual cambiando $\theta$ por $O$ o por $\Omega$ .

Polinomios: un polinomio de grado $k$ es $\theta(n^k)$ .
Regla de la suma: $\theta(f(n)) + \theta(g(n)) = \theta(\max(f(n), g(n)))$ . Ejemplo: $\theta(n^2) + \theta(n) = \theta(n^2)$ .
Regla del producto: $\theta(f(n)) \cdot \theta(g(n)) = \theta(f(n) \cdot g(n))$ . Ejemplo: $\theta(n) \cdot \theta(n^2) = \theta(n^3)$ .
Cerrado para la suma: si $f, g \in \theta(h(n))$ , entonces $f + g \in \theta(h(n))$ . Ejemplo: $(3n+3) + (25n+8) = 28n + 11 \in \theta(n)$ .
No cerrado para el producto: si $f, g \in \theta(h(n))$ , $f \cdot g$ no tiene por qué estar en $\theta(h(n))$ . Ejemplo: $(3n+3)(25n+8) \in \theta(n^2)$ , no $\theta(n)$ .
Constantes: si $f \in \theta(h(n))$ , entonces $a f(n) + b \in \theta(h(n))$ para $a > 0$ . Ejemplo: $100(3n+3) + 7 \in \theta(n)$ .

Comparar órdenes con límites

$\displaystyle\lim_{n\to\infty} \frac{f(n)}{g(n)}$	Conclusión
$k \ne 0$ (constante)	$f \in \theta(g)$ y $g \in \theta(f)$
$\infty$	$f$ crece más rápido que $g$
$0$	$g$ crece más rápido que $f$

La base del logaritmo no importa

Para $a, b > 1$ : $\theta(\log_a n) = \theta(\log_b n)$ , porque

\lim_{n\to\infty} \frac{\log_a n}{\log_b n} = \lim_{n\to\infty} \frac{\log_a b \cdot \log_b n}{\log_b n} = \log_a b \ne 0

Por eso se escribe simplemente $\log n$ .

Sumas habituales

\sum_{i=1}^{n} 1 = n \qquad \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \qquad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \qquad \sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4}

Progresión aritmética ( $a_n = a_1 + (n-1)d$ ): $\displaystyle\sum_{i=1}^{n} a_i = \frac{n(a_1 + a_n)}{2}$
Progresión geométrica ( $a_n = a_1 r^{n-1}$ ): $\displaystyle\sum_{i=1}^{n} a_i = a_1\frac{r^n - 1}{r - 1}$
Linealidad: $\sum c\,f(i) = c \sum f(i)$ y $\sum (f(i) + g(i)) = \sum f(i) + \sum g(i)$

Suma	Orden (también vale con $O$ y $\Omega$ )
$\sum_{i=1}^{n} i^k$ , $k \in \mathbb{N}^+$	$\theta(n^{k+1})$
$\sum_{i=1}^{n} (n-i)^k$ , $k \in \mathbb{N}^+$	$\theta(n^{k+1})$
$\sum_{i=1}^{n} r^i$ , $r > 1$	$\theta(r^n)$
$\sum_{i=1}^{n} \frac{1}{i}$	$\theta(\log n)$
$\sum_{i=1}^{n} \frac{1}{r^i}$ , $r > 1$	$\theta(1)$

Cómo calcular la complejidad de un algoritmo

Talla: decidir de qué depende el tamaño del problema.
Instancias: ver si hay mejor y peor caso.
- Si el coste no depende de la instancia: se da con $\theta$ .
- Si depende: se da con $\Omega$ (mejor caso) y $O$ (peor caso).
Cuantificar:
- Algoritmos iterativos: contar los pasos significativos.
- Algoritmos recursivos: plantear y resolver una relación de recurrencia.

Mismo código, con y sin instancias

Funcion Ejemplo1 (v: vector enteros; n: entero) retorna (entero)
  m = 0;
  si (n = 0) retorna 1;
  si no
    para i = 1 hasta n hacer m = m + n; fpara
  fsi
  retorna m
ffuncion

Con la condición n = 0: no hay instancias, porque $n = 0$ es un valor de la talla. Coste $\theta(n)$ .
Cambiando la condición por par(v[n]): sí hay instancias, porque con $n$ fijo el coste depende del contenido del vector. Mejor caso constante y peor caso lineal: $\Omega(1)$ y $O(n)$ .

Algoritmos recursivos

Su coste se expresa de forma natural con una relación de recurrencia:

T(n) = \begin{cases} c_1 & \text{en el caso base} \\ T(s(n)) + p(n) + c_2 & \text{en otro caso} \end{cases}

donde $s(n) < n$ ; lo habitual es $s(n) = n - c$ o $s(n) = n / c$ , y $p(n)$ puede ser $0$ .

Hay varios métodos para resolverlas (sustitución, inducción, función generadora…). En la asignatura se usa el de sustitución o expansión: ir sustituyendo cada $T(\cdot)$ por su definición hasta ver el término general, y llegar al caso base.

Factorial

Función Factorial(n: entero) retorna (entero)
  si (n = 0) entonces retorna 1
  sino retorna n * Factorial(n-1)
  fsi
ffuncion

Talla $n$ , sin instancias. Recurrencia:

T(n) = \begin{cases} c_1 & n = 0 \\ T(n-1) + c_2 & n > 0 \end{cases}

Expandiendo: $T(n) = T(n-1) + c_2 = T(n-2) + 2c_2 = \dots = T(n-i) + i\,c_2$ . Se llega a la base cuando $n - i = 0$ , es decir, $i = n$ : $T(n) = T(0) + n c_2 = c_1 + n c_2 \in \theta(n)$ .

Recurrencias inmanejables: acotar

A veces la expansión se complica tanto que no se puede resolver. Entonces se busca la menor cota superior y la mayor cota inferior posibles, sustituyendo la recurrencia por otras dos más sencillas que la acoten.

Dos llamadas de tamaños distintos

Función Ejemplo(n: entero) retorna (entero)
  si n = 1 entonces retorna 1
  sino retorna n * Ejemplo(n-1) * Ejemplo(n div 2)
  fsi
ffuncion

T(n) = \begin{cases} c_1 & n = 1 \\ T(n-1) + T(n \operatorname{div} 2) + c_2 & n \ne 1 \end{cases}

Cota inferior: cambiar $T(n-1)$ por $T(n \operatorname{div} 2)$ , que es más pequeño: $T_1(n) = 2T_1(n \operatorname{div} 2) + c_2 \in \theta(n)$ .
Cota superior: cambiar $T(n \operatorname{div} 2)$ por $T(n-1)$ , que es más grande: $T_2(n) = 2T_2(n-1) + c_2 \in \theta(2^n)$ .

Por tanto, $T(n) \in \Omega(n)$ y $T(n) \in O(2^n)$ .

Modelos generales de recurrencia

Sirven para comprobar que los cálculos hechos a mano están bien.

En los exámenes no se puede usar esta tabla

Salvo que se diga lo contrario, la complejidad hay que obtenerla resolviendo la recurrencia; la tabla es solo para comprobar el resultado.

Sustracción (el problema se reduce restando $b$ ):

T(n) = \begin{cases} c\,n^k & 0 \le n < b \\ a\,T(n-b) + c\,n^k & n \ge b \end{cases} \qquad\Longrightarrow\qquad T(n) \in \begin{cases} \theta(n^k) & a < 1 \\ \theta(n^{k+1}) & a = 1 \\ \theta\!\left(a^{\,n \operatorname{div} b}\right) & a > 1 \end{cases}

División (el problema se reduce dividiendo entre $b$ ):

T(n) = \begin{cases} c\,n^k & 1 \le n < b \\ a\,T(n/b) + c\,n^k & n \ge b \end{cases} \qquad\Longrightarrow\qquad T(n) \in \begin{cases} \theta(n^k) & a < b^k \\ \theta(n^k \log n) & a = b^k \\ \theta\!\left(n^{\log_b a}\right) & a > b^k \end{cases}

Aquí $a$ es el número de llamadas recursivas, $b$ cuánto se reduce el problema y $n^k$ el coste del trabajo no recursivo. El caso $a < 1$ en sustracción no tiene utilidad práctica; está por completitud.

Comprobaciones

Factorial: sustracción con $a = 1$ , $b = 1$ , $k = 0$ : $\theta(n^{1}) = \theta(n)$ . ✓
$T_1$ : división con $a = 2$ , $b = 2$ , $k = 0$ ; $a > b^k = 1$ : $\theta(n^{\log_2 2}) = \theta(n)$ . ✓
$T_2$ : sustracción con $a = 2$ , $b = 1$ : $\theta(2^n)$ . ✓

Límites del criterio asintótico

¿Es mejor un algoritmo de coste $3n^3$ o uno de $600n^2$ ? Asintóticamente, el segundo, porque $O(n^2) \subset O(n^3)$ . Pero eso es para $n$ suficientemente grande: $3n^3 \ge 600n^2$ solo cuando $n \ge 200$ .

Si casi todos los problemas reales tienen $n < 200$ , conviene el de $3n^3$ .
Para ir bien con cualquier talla, se pueden combinar: un programa que llame a uno u otro según $n$ .

Otras cosas a tener en cuenta:

Un algoritmo teóricamente mejor puede esconder una constante enorme que lo haga peor en la práctica.
Si se va a usar pocas veces, puede compensar uno menos eficiente pero más rápido de desarrollar: el coste incluye desarrollo y mantenimiento, no solo ejecución.
Ganar tiempo puede costar memoria.

Como cualquier ingeniero, el diseñador tiene que buscar un compromiso entre todos estos factores (talla, frecuencia de uso…).