¿Qué representa exactamente la notación Ψ grande?

Primero, comprendamos qué son la gran O, la gran Theta y la gran Omega. Todos ellos son conjuntos de funciones.

Big O da un límite asintótico superior , mientras que Big Omega da un límite inferior. Big Theta ofrece ambas cosas.

Todo lo que es Ө(f(n))también lo es O(f(n)), pero no al revés.
T(n)se dice que está en Ө(f(n))si está tanto en O(f(n))como en Omega(f(n)).
En terminología de conjuntos, Ө(f(n))es la intersección de O(f(n))yOmega(f(n))

Por ejemplo, el peor caso de clasificación por fusión es ambos O(n*log(n))y Omega(n*log(n)), por lo tanto, también es Ө(n*log(n)), pero también es O(n^2), ya que n^2es asintóticamente "más grande" que él. Sin embargo, no lo es Ө(n^2), ya que el algoritmo no lo es Omega(n^2).

Una explicación matemática un poco más profunda.

O(n)es el límite superior asintótico. Si T(n)es O(f(n)), significa que a partir de cierto n0, existe una constante Ctal que T(n) <= C * f(n). Por otro lado, el gran Omega dice que existe una constante C2tal que T(n) >= C2 * f(n))).

¡No confundir!

No debe confundirse con el análisis de los casos peor, mejor y promedio: las tres notaciones (Omega, O, Theta) no están relacionadas con el análisis de algoritmos de los casos mejor, peor y promedio. Cada uno de estos se puede aplicar a cada análisis.

Generalmente lo usamos para analizar la complejidad de los algoritmos (como el ejemplo anterior de clasificación por combinación). Cuando decimos "El algoritmo A es O(f(n))", lo que realmente queremos decir es "La complejidad del algoritmo según el análisis del peor ^de los casos es O(f(n))", es decir, escala "similar" (o formalmente, no peor que) la función f(n).

¿Por qué nos importa el límite asintótico de un algoritmo?

Bueno, hay muchas razones para ello, pero creo que las más importantes son:

1. Es mucho más difícil determinar la función de complejidad exacta , por lo que "comprometemos" las notaciones O grande/Theta grande, que son suficientemente informativas en teoría.
2. El número exacto de operaciones también depende de la plataforma . Por ejemplo, si tenemos un vector (lista) de 16 números. ¿Cuántas operaciones serán necesarias? La respuesta es, depende. Algunas CPU permiten adiciones de vectores, mientras que otras no, por lo que la respuesta varía entre diferentes implementaciones y diferentes máquinas, lo cual es una propiedad no deseada. Sin embargo, la notación con O grande es mucho más constante entre máquinas e implementaciones.

Para demostrar este problema, eche un vistazo a los siguientes gráficos:

Está claro que f(n) = 2*nes "peor" que f(n) = n. Pero la diferencia no es tan drástica como lo es con respecto a la otra función. Podemos ver que f(n)=lognrápidamente se vuelve mucho más bajo que las otras funciones, y f(n) = n^2rápidamente se vuelve mucho más alto que las demás.
Entonces, por las razones anteriores, "ignoramos" los factores constantes (2* en el ejemplo de gráficos) y tomamos solo la notación O grande.

En el ejemplo anterior, f(n)=n, f(n)=2*nambos estarán en O(n)y en Omega(n)y, por lo tanto, también estarán en Theta(n).
Por otro lado, f(n)=lognestará dentro O(n)(es "mejor" que f(n)=n), pero NO estará dentro Omega(n), y por lo tanto NO estará dentro Theta(n).
Simétricamente, f(n)=n^2estará en Omega(n), pero NO en y O(n), por lo tanto, también NO Theta(n).

¹ Generalmente, aunque no siempre. cuando falta la clase de análisis (peor, promedio y mejor), en realidad nos referimos al peor de los casos.

Sep 09 '2012 12:09 amit