Notación asintótica O, Ω y θ y relaciones de recurrencia

Abrir el simulador

Compara dos costes con el límite del cociente, busca c y n₀ y resuelve recurrencias con su árbol de llamadas.

Un algoritmo tarda

3n^2 + 4n + 4

pasos y otro

4n + 4

. ¿Cuál es mejor? Para tallas pequeñas la respuesta depende de los detalles, pero a partir de cierto tamaño siempre gana el segundo, porque crece más despacio. La notación asintótica sirve para decir eso con precisión: olvida las constantes y las tallas pequeñas y se queda con lo que decide en problemas grandes, cómo crece el coste. Es el idioma con el que se comparan algoritmos.

Lo que vas a aprender

Qué significan $O$ , $\Omega$ y $\theta$ , y cómo se demuestra que una función está en una de ellas.
La jerarquía de órdenes, de $O(1)$ a $O(n^n)$ .
Comparar dos costes con el límite de su cociente.
Las reglas de la suma y del producto, y las sumas que aparecen al contar pasos.
Plantear la recurrencia de un algoritmo recursivo y resolverla por sustitución.
Comprobar el resultado con los modelos generales de sustracción y división.

Cómo se usa el simulador

Pestaña «Comparar órdenes»

Control	Qué hace
f(n) y g(n)	Los dos costes, escritos en función de $n$ : `3n^3`, `n log(n)`, `2^n`, `sqrt(n)`…
Ejemplos	Parejas típicas: $3n^3$ frente a $600n^2$ , la base del logaritmo, $2^n$ frente a $n^3$ …
Escala	Eje vertical lineal o logarítmico, para ver juntas funciones muy distintas
n · hasta	Hasta qué talla se dibuja (de 10 a un millón)

El panel de la derecha da el límite del cociente

f/g

y la conclusión, los valores de

c

n_0

que cumplen la definición de

O

y de

\Omega

(con

c \cdot g(n)

dibujada a trazos) y la talla en la que las dos curvas se cruzan. Pestaña «Recurrencias»

Control	Qué hace
Modelo	Sustracción, $T(n - b)$ , o división, $T(n / b)$
a	Número de llamadas recursivas
b	Cuánto se resta o entre cuánto se divide la talla
k	Exponente del trabajo no recursivo, $c\,n^k$
Ejemplos	Factorial, selección, búsqueda binaria, mergesort, Karatsuba…

Se muestran la recurrencia, su expansión tras

i

pasos, el coste de cada nivel del árbol de llamadas, la solución según la tabla y una comprobación numérica:

T(n)

calculado con la recurrencia y dividido entre el orden de la solución, que debe tender a una constante.

El logaritmo se escribe log y es el neperiano. La base no cambia el orden; si quieres

\log_2 n

exacto, escribe log(n)/log(2).

Fundamentos teóricos

Talla, paso y principio de invarianza

La talla es lo que mide el tamaño del problema: el número de elementos de un vector, las dimensiones de una matriz, el propio número. Un paso es un fragmento de código que tarda un tiempo acotado por una constante, sin importar la talla: una suma, una comparación, una asignación. El coste se mide en pasos, no en segundos. Según el principio de invarianza, dos implementaciones del mismo algoritmo solo se diferencian en una constante multiplicativa. Un ordenador diez veces más rápido divide el tiempo entre diez, pero no cambia la forma en que crece. Por eso las constantes se ignoran y se estudia el orden.

Las tres notaciones

Sean

f, g: \mathbb{N} \to \mathbb{R}^+

, con

f(n)

el coste del algoritmo. Cota superior, $O$ :

g

domina a

f

a partir de un punto.

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

Cota inferior, $\Omega$ : hay un múltiplo de

g

que

f

nunca baja.

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

Orden exacto, $\theta$ : las dos a la vez.

f(n) \in \theta(g(n)) \iff \exists\, c_1, c_2, n_0 : \ c_1\, g(n) \le f(n) \le c_2\, g(n) \ \ \forall n \ge n_0

Para demostrar que

f \in O(g)

basta con dar una pareja

c

n_0

que funcione. Por ejemplo,

3n + 2 \in O(n)

porque con

c = 4

se cumple

3n + 2 \le 4n

para todo

n \ge 2

. Es justo lo que calcula el simulador.

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)

Tipo	Orden	Ejemplo
Constante	$O(1)$	Acceder a un elemento de un vector
Logarítmica	$O(\log n)$	Búsqueda binaria
Lineal	$O(n)$	Búsqueda secuencial
Superlineal	$O(n \log n)$	Mergesort
Cuadrática	$O(n^2)$	Ordenación por selección
Cúbica	$O(n^3)$	Producto de matrices clásico
Exponencial	$O(2^n)$	Probar todos los subconjuntos

Como

O(n) \subset O(n^2)

, la función

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

\Omega

las inclusiones van al revés.

Comparar órdenes con límites

La forma más rápida de comparar dos funciones es el límite de su cociente:

$\displaystyle\lim_{n\to\infty} \frac{f(n)}{g(n)}$	Conclusión
$k$ , con $0 \lt k \lt \infty$	$f \in \theta(g)$ : el mismo orden
$\infty$	$f$ crece más deprisa: $f \in \Omega(g)$ y $f \notin O(g)$
$0$	$g$ crece más deprisa: $f \in O(g)$ y $f \notin \Omega(g)$

Con este criterio se ve que la base del logaritmo no importa: para

a, b > 1

\lim_{n\to\infty} \frac{\log_a n}{\log_b n} = \log_a b \ne 0 \quad\Longrightarrow\quad \theta(\log_a n) = \theta(\log_b n)

Propiedades

Todas valen igual con

O

, con

\Omega

y con

\theta

Polinomios: un polinomio de grado $k$ es $\theta(n^k)$ . Se queda el término de mayor grado.
Regla de la suma: $\theta(f) + \theta(g) = \theta(\max(f, g))$ . Dos bucles seguidos cuestan lo que el más caro.
Regla del producto: $\theta(f) \cdot \theta(g) = \theta(f \cdot g)$ . Un bucle dentro de otro multiplica.
Constantes: si $f \in \theta(h)$ , también $a f + b \in \theta(h)$ para $a > 0$ .

Sumas habituales

Al contar los pasos de bucles anidados aparecen siempre las mismas sumas:

\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}

Suma	Orden
$\sum_{i=1}^{n} i^k$	$\theta(n^{k+1})$
$\sum_{i=1}^{n} r^i$ , con $r > 1$	$\theta(r^n)$
$\sum_{i=1}^{n} 1/i$	$\theta(\log n)$
$\sum_{i=1}^{n} 1/r^i$ , con $r > 1$	$\theta(1)$

Mejor y peor caso

Si con la talla fija el coste cambia según los datos (las instancias), se estudian el mejor y el peor caso. Entonces el coste se da con

\Omega

para el mejor caso y con

O

para el peor. La búsqueda secuencial es

\Omega(1)

(el elemento está el primero) y

O(n)

(no está). Si no hay instancias, se da directamente con

\theta

Algoritmos recursivos: relaciones de recurrencia

El coste de un algoritmo recursivo se escribe en función de sí mismo:

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

donde

a

es el número de llamadas,

s(n)

la talla de cada una (normalmente

n - b

n/b

) y

p(n)

el trabajo que no es recursivo. Se resuelve por sustitución: se cambia

T(\cdot)

por su definición una y otra vez hasta ver el término general, y se llega al caso base.

Modelos generales de recurrencia

Sustracción (la talla se reduce restando

b

T(n) = a\,T(n - b) + c\,n^k \quad\Longrightarrow\quad T(n) \in \begin{cases} \theta(n^k) & a \lt 1 \\ \theta(n^{k+1}) & a = 1 \\ \theta(a^{\,n \operatorname{div} b}) & a \gt 1 \end{cases}

División (la talla se divide entre

b

T(n) = a\,T(n / b) + c\,n^k \quad\Longrightarrow\quad T(n) \in \begin{cases} \theta(n^k) & a \lt b^k \\ \theta(n^k \log n) & a = b^k \\ \theta(n^{\log_b a}) & a \gt b^k \end{cases}

En los exámenes de Algoritmia la tabla no se puede usar, salvo que se diga lo contrario: la complejidad se obtiene resolviendo la recurrencia. La tabla sirve para comprobar el resultado.

Por qué salen esos tres casos: el árbol de llamadas

En el modelo de división, el nivel

j

del árbol tiene

a^j

llamadas de talla

n/b^j

, y cada una hace

c\,(n/b^j)^k

pasos. El nivel entero cuesta:

a^j \cdot c\left(\frac{n}{b^j}\right)^k = c\,n^k \left(\frac{a}{b^k}\right)^j

Es una progresión geométrica de razón

a/b^k

, con

\log_b n

niveles:

Si $a \lt b^k$ , cada nivel cuesta menos que el anterior y manda la raíz: $\theta(n^k)$ .
Si $a = b^k$ , todos los niveles cuestan lo mismo, $c\,n^k$ , y hay $\log_b n$ : $\theta(n^k \log n)$ .
Si $a \gt b^k$ , cada nivel cuesta más y mandan las hojas, que son $a^{\log_b n} = n^{\log_b a}$ .

El simulador dibuja una barra por nivel con su coste: se ve de un vistazo cuál de los tres casos es.

Ejemplos resueltos

Ejemplo 1 · Demostrar una cota con c y n₀

Demuestra que

10n^2 + 4n + 2 \in \theta(n^2)

.Cota inferior:

10n^2 + 4n + 2 \ge 10n^2

para todo

n \ge 0

, así que vale

c_1 = 10

.Cota superior: para

n \ge 1

4n \le 4n^2

2 \le 2n^2

, luego

10n^2 + 4n + 2 \le 16n^2

. Vale

c_2 = 16

con

n_0 = 1

.Con el límite es inmediato:

\lim \dfrac{10n^2 + 4n + 2}{n^2} = 10

, una constante distinta de cero. El simulador encuentra

c = 11

con

n_0 = 5

: también vale, porque no hay una única pareja.

Ejemplo 2 · ¿3n³ o 600n²?

Asintóticamente es mejor

600n^2

, porque

\lim \dfrac{3n^3}{600n^2} = \lim \dfrac{n}{200} = \infty

.Pero

3n^3 \ge 600n^2 \iff n \ge 200

. Para tallas menores que 200, el algoritmo cúbico da menos pasos. Si casi todos los problemas reales son pequeños, conviene el cúbico; para cualquier talla, se pueden combinar los dos y llamar a uno u otro según

n

Ejemplo 3 · Factorial por sustitución

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

T(n) = \begin{cases} c_1 & n = 0 \\ T(n-1) + c_2 & n \gt 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 al caso base cuando

i = n

T(n) = c_1 + n\,c_2 \in \theta(n)

Comprobación: sustracción con

a = 1

b = 1

k = 0

\theta(n^{k+1}) = \theta(n)

. ✓

Ejemplo 4 · Mergesort

Divide el vector en dos mitades, ordena cada una y las mezcla en tiempo lineal:

T(n) = 2\,T(n/2) + c\,n

Expandiendo:

T(n) = 2^i\,T(n/2^i) + i\,c\,n

. El caso base se alcanza con

n/2^i = 1

, es decir,

i = \log_2 n

T(n) = n\,T(1) + c\,n\log_2 n \in \theta(n \log n)

Comprobación: división con

a = 2

b = 2

k = 1

; como

a = b^k = 2

, sale

\theta(n \log n)

. ✓ En el árbol, los

\log_2 n

niveles cuestan

c\,n

cada uno.

Ejemplo 5 · Una recurrencia que hay que acotar

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

T(n) = T(n-1) + T(n \operatorname{div} 2) + c

no se resuelve directamente. Se acota por los dos lados:

Por debajo, cambiando $T(n-1)$ por el más pequeño $T(n \operatorname{div} 2)$ : $T_1(n) = 2T_1(n/2) + c \in \theta(n)$ .
Por arriba, cambiando $T(n \operatorname{div} 2)$ por el más grande $T(n-1)$ : $T_2(n) = 2T_2(n-1) + c \in \theta(2^n)$ .

Conclusión:

T(n) \in \Omega(n)

T(n) \in O(2^n)

. Comprueba las dos en el simulador con «Dos llamadas n/2» y «Dos llamadas n − 1».

Experimenta con el simulador

Encuentra el cruce

Carga «3n³ frente a 600n²» y sube la talla máxima. ¿Dónde se cruzan? Cambia 600 por 6000: ¿cómo se mueve el cruce?

La base no importa

Carga «Base del logaritmo». ¿A qué constante tiende el cociente? Compárala con

\log_2 10

Polinómica frente a exponencial

Compara

2^n

con

n^{10}

en escala logarítmica. ¿A partir de qué talla gana la exponencial? ¿Y con

n^{20}

Los tres casos del modelo de división

Con

b = 2

k = 1

, pon

a = 1

a = 2

a = 4

. Mira cómo cambian las barras del árbol: ¿dónde está el coste en cada caso?

Comprobación numérica

En Karatsuba, el cociente

T(n)/n^{\log_2 3}

tiende a una constante. Cambia mentalmente la solución por

n^2

: ¿qué haría el cociente?

Errores frecuentes

Dar una cota que no es la más ajustada. Decir que la búsqueda binaria es $O(n)$ es cierto pero inútil: es $O(\log n)$ .
Confundir $O$ con «peor caso» y $\Omega$ con «mejor caso». Son cotas de funciones; se usan para el peor y el mejor caso, pero cualquier función tiene las tres.
Confundir instancia con talla. Que el algoritmo haga algo distinto cuando $n = 0$ no es una instancia: es un valor de la talla.
Aplicar el modelo de división a una recurrencia de sustracción, o al revés. $T(n-1)$ y $T(n/2)$ dan resultados completamente distintos.
Olvidar el trabajo no recursivo. En mergesort, la mezcla es lo que da el factor $n$ de cada nivel.
Creer que $\theta(\log n) \ne \theta(\log_2 n)$ . Todas las bases dan el mismo orden.

Límites del criterio asintótico

La notación asintótica describe tallas suficientemente grandes. En la práctica también importan:

Las constantes ocultas: un algoritmo teóricamente mejor puede esconder una constante enorme. La multiplicación de matrices de Strassen, $\theta(n^{2{,}81})$ , solo compensa con matrices bastante grandes.
La talla real de los problemas: si siempre son pequeños, puede ganar el algoritmo asintóticamente peor.
La memoria: ganar tiempo suele costar espacio.
El coste de desarrollo: si un programa se usa pocas veces, puede compensar uno menos eficiente pero más sencillo.

Un poco de historia

La notación

O

la introdujo el matemático Paul Bachmann en 1894, y Edmund Landau la popularizó en teoría de números; por eso se llaman símbolos de Landau. En 1976, Donald Knuth propuso usar

\Omega

\theta

tal como se usan hoy en informática. El teorema que resuelve las recurrencias de división se conoce como teorema maestro desde que lo recogió el libro de Cormen, Leiserson, Rivest y Stein (1990), aunque se basa en un trabajo de Bentley, Haken y Saxe de 1980.

Preguntas frecuentes

¿Se escribe f ∈ O(g) o f = O(g)?

O(g)

es un conjunto de funciones, así que lo correcto es

f \in O(g)

. La forma

f = O(g)

es una costumbre muy extendida, pero no es una igualdad: no se puede leer al revés.

¿Qué pasa si el límite del cociente no existe?

El criterio del límite no decide, y hay que volver a la definición. Por ejemplo,

f(n) = n

para

n

par y

f(n) = n^2

para

n

impar está en

O(n^2)

y en

\Omega(n)

, pero no en

\theta

de ninguna de las dos.

¿Por qué Fibonacci recursivo es exponencial?

Porque cada llamada hace dos más,

T(n) = T(n-1) + T(n-2) + c

, y el árbol tiene un número de nodos que crece como

\varphi^n

, con

\varphi \approx 1{,}618

. Está entre

\theta(2^{n/2})

\theta(2^n)

, como se ve acotando por los dos lados.

¿Sirve para la memoria igual que para el tiempo?

Sí. Todo lo que se dice del coste temporal vale para el espacial: basta con contar celdas de memoria en lugar de pasos.

¿Qué orden tiene un bucle que divide i entre 2 en cada vuelta?

Logarítmico: si

i

empieza en

n

y se divide entre 2 hasta llegar a 1, da

\log_2 n

vueltas. Es lo que pasa en la búsqueda binaria.

Temas relacionados

Mejor y peor caso

Análisis experimental: contar operaciones para cada talla.

Divide y vencerás

Algoritmos que se resuelven con recurrencias de división.

Algoritmos de ordenación

Burbuja, selección, inserción, mergesort y quicksort comparados.

Matemáticas

Física

Química

Electrónica

Programación

Inglés

Infantil

Notación asintótica O, Ω y θ y relaciones de recurrencia

Abrir el simulador

Lo que vas a aprender

Cómo se usa el simulador

Fundamentos teóricos

Talla, paso y principio de invarianza

Las tres notaciones

Jerarquía de órdenes

Comparar órdenes con límites

Propiedades

Sumas habituales

Mejor y peor caso

Algoritmos recursivos: relaciones de recurrencia

Modelos generales de recurrencia

Por qué salen esos tres casos: el árbol de llamadas

Ejemplos resueltos

Experimenta con el simulador

Errores frecuentes

Límites del criterio asintótico

Un poco de historia

Preguntas frecuentes

Temas relacionados

Mejor y peor caso

Divide y vencerás

Algoritmos de ordenación

Abrir el simulador

​Lo que vas a aprender

​Cómo se usa el simulador

​Fundamentos teóricos

​Talla, paso y principio de invarianza

​Las tres notaciones

​Jerarquía de órdenes

​Comparar órdenes con límites

​Propiedades

​Sumas habituales

​Mejor y peor caso

​Algoritmos recursivos: relaciones de recurrencia

​Modelos generales de recurrencia

​Por qué salen esos tres casos: el árbol de llamadas

​Ejemplos resueltos

​Experimenta con el simulador

​Errores frecuentes

​Límites del criterio asintótico

​Un poco de historia

​Preguntas frecuentes

​Temas relacionados

Mejor y peor caso

Divide y vencerás

Algoritmos de ordenación

Lo que vas a aprender

Cómo se usa el simulador

Fundamentos teóricos

Talla, paso y principio de invarianza

Las tres notaciones

Jerarquía de órdenes

Comparar órdenes con límites

Propiedades

Sumas habituales

Mejor y peor caso

Algoritmos recursivos: relaciones de recurrencia

Modelos generales de recurrencia

Por qué salen esos tres casos: el árbol de llamadas

Ejemplos resueltos

Experimenta con el simulador

Errores frecuentes

Límites del criterio asintótico

Un poco de historia

Preguntas frecuentes

Temas relacionados