Programación · Algoritmia

Notación asintótica

O, Ω y θ con dos funciones cualesquiera, y el coste de un algoritmo recursivo a partir de su recurrencia.

Costes

en función de la talla n

f(n)g(n)

Potencias con ^, raíz con sqrt( ) o √, logaritmo con log (neperiano: la base no cambia el orden). Para log₂ escribe log(n)/log(2).

Crecimiento

n · hasta316

━ f(n) · ━ g(n)

Funciones

f (n) = 3 n^{3}

g (n) = 600 n^{2}

Límite del cociente

n \to \infty lim \frac{f ( n )}{g ( n )} = \infty \Rightarrow f \in Ω (g), f \in / O (g)

f crece más deprisa que g: para tallas grandes acaba superándola, se multiplique g por lo que se multiplique.

f ∉ O(g): no hay c ni n₀ que valgan: f acaba superando a cualquier múltiplo de g.

f ∈ Ω(g): f(n) ≥ g(n) para todo n ≥ 200 (c = 1).

Se cruzan en n ≈ 200. Antes de ese punto f da menos pasos; después, g. Si casi todas las tallas reales son menores, puede convenir el algoritmo asintóticamente peor.

Jerarquía de órdenes

O (1) \subset O (lo g n) \subset O (n) \subset O (n) \subset O (n lo g n)

\subset O (n^{2}) \subset O (n^{3}) \subset O (2^{n}) \subset O (n^{n})

Qué es y cómo se usa

La notación asintótica compara cómo crece el coste de un algoritmo con la talla del problema, sin fijarse en las constantes ni en las tallas pequeñas. f ∈ O(g) significa que, a partir de un n₀, f(n) ≤ c·g(n): g es una cota superior. Ω es la cota inferior y θ el orden exacto, cuando se cumplen las dos.

En la primera pestaña escribes dos costes y el simulador calcula el límite de su cociente, que decide la relación: una constante distinta de cero da θ, infinito da Ω y cero da O. También busca la c y el n₀ de la definición y el punto en que las dos curvas se cruzan.

La segunda pestaña resuelve recurrencias de sustracción, T(n) = a·T(n − b) + c·nᵏ, y de división, T(n) = a·T(n/b) + c·nᵏ, con la tabla de modelos generales. El árbol de llamadas muestra el coste de cada nivel: si manda la raíz, si todos cuestan lo mismo o si mandan las hojas.

Ejemplo resuelto

Mergesort divide el vector en dos mitades, se llama en cada una y mezcla en tiempo lineal. ¿Cuál es su coste?

Recurrencia: T(n) = 2·T(n/2) + c·n, modelo de división con a = 2, b = 2 y k = 1.
Se compara a con bᵏ: 2 = 2¹, así que estamos en el caso a = bᵏ.
Cada nivel del árbol cuesta c·n y hay log₂ n niveles.
T(n) ∈ θ(nᵏ·log n) = θ(n log n).

T(n) ∈ θ(n log n)

Preguntas frecuentes

¿Por qué no importa la base del logaritmo?

Porque log_a n / log_b n = log_a b, una constante. Cambiar de base solo multiplica por una constante, y las constantes no cambian el orden. Por eso se escribe simplemente log n.

Si 3n³ es peor que 600n², ¿por qué a veces conviene?

Porque la notación asintótica habla de tallas grandes. 3n³ solo supera a 600n² a partir de n = 200; si los problemas reales son más pequeños, el algoritmo cúbico es más rápido.

¿Cuál es la diferencia entre O y θ?

O es solo una cota superior: 3n + 2 está en O(n), pero también en O(n²). θ es el orden exacto: 3n + 2 está en θ(n) y no en θ(n²). Siempre se da la cota más ajustada.

¿Puedo usar la tabla de recurrencias en el examen?

Normalmente no: la complejidad hay que obtenerla resolviendo la recurrencia, por ejemplo por sustitución. La tabla sirve para comprobar que el resultado es correcto.