big-o - problems - big o space complexity

¿Alguien podría explicar Big O versus Big Omega vs Big Theta?

Question

Posible duplicado:
Notación Big Theta: ¿qué representa exactamente Theta grande?

Lo entiendo en teoría, supongo, pero lo que estoy teniendo problemas para captar es la aplicación de los tres.

En la escuela, siempre utilizamos Big O para denotar la complejidad de un algoritmo. El tipo de burbuja fue O (n ^ 2) por ejemplo.

Ahora, después de leer más teoría, entiendo que Big Oh no es la única medida, hay al menos otras dos interesantes.

Pero esta es mi pregunta:

Big O es el límite superior, Big Omega es el límite inferior, y Big Theta es una mezcla de los dos. Pero, ¿qué significa eso conceptualmente? Entiendo lo que significa en un gráfico; He visto un millón de ejemplos de eso. Pero, ¿qué significa para la complejidad del algoritmo? ¿Cómo se combina un "límite superior" o un "límite inferior"?

Supongo que simplemente no entiendo su aplicación. Entiendo que si se multiplica por alguna constante c, si después de algún valor n_0 f (x) es mayor que g (x), f (x) se considera O (g (x)). Pero, ¿qué significa eso prácticamente? ¿Por qué estaríamos multiplicando f (x) por algún valor c? Demonios, pensé que con la notación Big O los múltiplos no importaban.

Answer 1

La gran notación O, y sus parientes, la gran Theta, la gran Omega, la pequeña O y la pequeña omega son formas de decir algo acerca de cómo se comporta una función en un punto límite (por ejemplo, cuando se acerca al infinito, pero también cuando se acerca 0, etc.) sin decir mucho más sobre la función. Se usan comúnmente para describir el espacio de ejecución y el tiempo de los algoritmos, pero también se pueden ver en otras áreas de las matemáticas con respecto al comportamiento asintótico.

La definición semi-intuitiva es la siguiente:

Se dice que una función g (x) es O (f (x)) si "desde algún punto en adelante", g (x) es menor que c * f (x), donde c es una constante.

Las otras definiciones son similares, Theta exige que g (x) esté entre dos múltiplos constantes de f (x), Omega exigente g (x)> c * f (x), y las versiones pequeñas exigen que esto sea cierto para todos constantes.

Pero, ¿por qué es interesante decir, por ejemplo, que un algoritmo ha ejecutado el tiempo de O (n ^ 2)?

Es interesante principalmente porque, en la informática teórica, estamos más interesados ​​en cómo los algoritmos se comportan para grandes entradas. Esto es cierto porque en entradas pequeñas los tiempos de ejecución del algoritmo pueden variar mucho dependiendo de la implementación, la compilación, el hardware y otras cosas que no son realmente interesantes cuando se analiza teóricamente un algoritmo.

La tasa de crecimiento, sin embargo, generalmente depende de la naturaleza del algoritmo, y para mejorarlo necesita conocimientos más profundos sobre el problema que está tratando de resolver. Este es el caso, por ejemplo, de los algoritmos de clasificación, donde puede obtener un algoritmo simple (Clasificación de burbujas) para ejecutar en O (n ^ 2), pero para mejorar esto a O (n log n) necesita una idea realmente nueva. , como el que se introdujo en Merge Sort o Heap Sort.

Por otro lado, si tienes un algoritmo que se ejecuta en exactamente 5n segundos, y otro que se ejecuta en 1000n segundos (que es la diferencia entre un bostezo prolongado y un salto de inicio para n = 3, por ejemplo), cuando llegas a n = 1000000000000, la diferencia de escala parece menos importante. Sin embargo, si tienes un algoritmo que toma O (log n), deberías esperar log (1000000000000) = 12 segundos, quizás multiplicado por alguna constante, en lugar de los casi 317,098 años, que, sin importar cuán grande sea la constante es, es una escala completamente diferente.

Espero que esto aclare un poco las cosas. ¡Buena suerte con sus estudios!