algorithm - rapper - big o notation java

¿Cuál es la diferencia entre O, Ω y Θ? (5)

Θ denota un límite superior e inferior asintóticamente ajustado.

O denota un límite superior, pero este límite puede o no ser ajustado.
o denota un límite superior que no está apretado.

Ω denota un límite inferior, pero este límite puede o no ser ajustado.
ω denota un límite inferior que no está ajustado.

Estoy aprendiendo análisis de algoritmos. Tengo problemas para entender la diferencia entre O, Ω y Θ.

La forma en que se definen es la siguiente:

f(n) = O(g(n)) significa que c · g(n) es un límite superior en f(n) . Por lo tanto, existe una constante c tal que f(n) siempre es ≤ c · g(n) , para n suficientemente grande (es decir, n ≥ n0 para alguna constante n0 ).
f(n) = Ω(g(n)) significa que c · g(n) es un límite inferior en f(n) . Por lo tanto, existe una constante c tal que f(n) siempre es ≥ c · g(n) , para todos n ≥ n0 .
f(n) = Θ(g(n)) significa que c1 · g(n) es un límite superior en f(n) y c2 · g(n) es un límite inferior en f(n) , para todos n ≥ n0 . Por lo tanto, existen constantes c1 y c2 tales que f(n) ≤ c1 ·g(n) y f(n) ≥ c2 ·g(n) . Esto significa que g(n) proporciona un límite bonito y ajustado en f(n) .

La forma en que he entendido esto es:

O(f(n)) da la peor complejidad de una función / algoritmo dado.
Ω(f(n)) proporciona la mejor complejidad de caso de una función / algoritmo dado.
Θ(f(n)) da una complejidad de caso promedio de una función / algoritmo dado.

Por favor, corríjame si estoy equivocado. Si es así, la complejidad del tiempo de cada algoritmo debe expresarse en las tres notaciones. Pero observé que se expresa como O, Ω o Θ; ¿Por qué no los tres?

Es importante recordar que la notación, ya sea O, Ω o Θ, expresa el crecimiento asintótico de una función ; no tiene nada intrínsecamente que ver con los algoritmos per se . La función en cuestión puede ser la "complejidad" (tiempo de ejecución) de un algoritmo, ya sea en el peor de los casos, en el mejor de los casos o en el promedio, pero la notación es independiente de dónde proviene la función.

Por ejemplo, la función f (n) = 3n ² +5 es:

O (n ² ), también es O (n ² log n), O (n ³ ), O (n ⁴ ), etc., pero no es O (n).
Ω (n ² ), también es Ω (n log n), Ω (n), etc., pero no es Ω (n ³ ).
Θ (n ² ). Ni siquiera es Θ (n ² log n) o Θ (n ² / log n).

Ahora, por lo general, la función considerada es la complejidad del peor caso de un algoritmo, y la notación de los tres que se usa depende de lo que queramos decir al respecto y de qué tan cuidadosamente hacemos el análisis. Por ejemplo, podemos observar que debido a que hay dos bucles anidados, el tiempo de ejecución en el peor de los casos es a lo sumo O (n ² ), sin importar si esto se logra realmente para alguna entrada. (Por lo general, es obvio que lo es). O bien, podemos decir que el peor tiempo de ejecución de la clasificación es Ω (n log n), porque debe haber algunas entradas para las que debe tomar al menos cn (log n) pasos. O bien, podemos observar un algoritmo de combinación de datos en particular y ver que toma la mayoría de los pasos O (n log n) en el peor de los casos y que alguna entrada hace que tome n registros n pasos, por lo que el tiempo de ejecución del peor de los casos es Θ (n log n).

Tenga en cuenta que en los tres ejemplos anteriores, seguía siendo el mismo tiempo de ejecución (en el peor de los casos) que se estaba analizando. En su lugar, podemos analizar el caso óptimo o el caso promedio, pero nuevamente, la notación de los tres que usamos depende de lo que queramos decir: si queremos otorgar un límite superior, un límite inferior o un límite estricto en el orden de Crecimiento de la misma función .

Estos son algunos de los recursos que realmente te ayudarán:

La notación Big-O a menudo se denomina complejidad de un algoritmo porque nos asegura que el algoritmo no tendrá un rendimiento sustancialmente mayor para n grande. Sin embargo, como se señaló anteriormente, el Big-O nos brinda una evaluación asintótica y nuestro algoritmo puede comportarse de manera diferente cuando se da cierta información. Por ejemplo, la ordenación rápida puede ser O (n ^ 2), cuando la matriz ya está ordenada. OTOH, la situación asintótica puede mejorarse en la práctica con una implementación ordenada.

Para lo que significan esos tres, vea la respuesta de Can Berk Güder.

Tenga en cuenta también que no tienen nada que ver con el mejor caso, el peor caso y el caso promedio. La clasificación de burbujas, por ejemplo, es best (n) mejor caso (porque si los datos ya están ordenados, solo se necesitan comparaciones n-1), y Θ (n ^ 2) peor caso. Es un caso promedio Θ (n ^ 2) suponiendo una entrada aleatoriamente barajada. Por lo tanto, ese caso promedio también es O (n ^ 2), y O (n ^ 3) y O (2 ^ n).

Entonces, O, Θ y Ω te dicen qué tipo de límite es. No te dicen a qué se limita el límite. En contexto, podría ser un límite para el mejor caso, el peor de los casos, el caso promedio o el algoritmo en su conjunto (todos los casos).

Por supuesto, si un algoritmo tiene Ω (g) mejor caso, entonces es then (g). Si tiene O (g) en el peor de los casos, es O (g). Entonces hay una relación allí. Pero si tiene un promedio de Θ (g), eso no dice casi nada sobre los mejores y los peores casos.

En cuanto a "¿por qué no los tres?".

Si su función es Θ (g), entonces también es O (g) y Ω (g). Así que no tiene mucho sentido proporcionar otros límites a lo largo de un límite Θ.

Cuando ve solo a uno de los otros, generalmente es porque solo nos preocupamos por un límite superior, o solo nos preocupamos por un límite inferior. Entonces, decimos que todos los tipos de comparación son necesariamente worst (n log n) el peor de los casos, y que el tipo de burbuja es O (n ^ 2) el peor de los casos, pero O (n) el mejor de los casos, porque no estamos tratando de describir completamente el tiempo complejidad, estamos expresando los límites que nos interesan en un contexto particular.

Y, en cualquier caso, la mayoría de las personas parecen ser perezosas y no quieren tener que escribir letras griegas. Sé quien soy. Así que solo decimos que los tipos de comparación son "en el mejor de los casos O (n log n)". Es realmente un abuso de notación, pero se entiende.