¿Por qué se enseña Big O en lugar de Big Theta?

21

La notación Big O proporciona un límite superior a una función, mientras que Big Theta proporciona un límite ajustado. Sin embargo, encuentro que la notación Big O es típicamente (e informalmente) enseñada y utilizada cuando realmente significan Big Theta.

por ejemplo, "Quicksort es O (N ^ 2)" puede convertirse en la afirmación mucho más fuerte "Quicksort es Θ (N ^ 2)"

Si bien el uso de Big O es técnicamente correcto, ¿no sería un uso más frecuente de Big Theta más expresivo y generaría menos confusión? ¿Hay alguna razón histórica por la cual esta Big O se usa más comúnmente?

Notas de Wikipedia :

Informalmente, especialmente en ciencias de la computación, a menudo se permite abusar de la notación Big O para describir un límite estrecho asintótico donde usar la notación Big Theta Θ podría ser más apropiado en un contexto dado.

notation big-o big-theta tskuzzy
fuente
3
Sé que esto realmente no pertenece a la pregunta, pero quicksort no es theta (N ^ 2). Es O (N ^ 2).
jsternberg
Big O es lo que los principiantes / no CS necesitan saber. Big Theta es lo que se cubre en una introducción a los algoritmos, que no serán tomados por todos los principales. Aquellos que hayan tenido una clase de algoritmos pueden leer más profundamente la notación Big O si lo desean. No estoy seguro de a qué se refiere la cita de Wikipedia. Con publicaciones académicas te cortarán la garganta en una conferencia si confundes a Big O y a Theta. Algunas personas pasan toda su vida persiguiendo a Theta y esos son problemas DUROS DUROS.
Trabajo
@jsternberg Técnicamente tienes razón. Esto también es cierto, pero no tiene sentido: "Quicksort en cualquier caso (peor, mejor, ...) es O (n ^ 100). Pero estoy de acuerdo con OP, debería ser más preciso: QuickSort en el peor de los casos es Theta (N ^ 2), el mejor caso de QuickSort es Theta (NlogN). Porque en cada caso obtendremos una función diferente.
Eldar

Respuestas:

26

Porque generalmente solo te interesa el peor de los casos al analizar el rendimiento. Por lo tanto, conocer el límite superior es suficiente.

Cuando se ejecuta más rápido de lo esperado para una entrada determinada, está bien, no es el punto crítico. Es sobre todo información insignificante.

Algunos algoritmos, como señaló @Peter Taylor, no tienen un límite estricto en absoluto. Vea la clasificación rápida, por ejemplo, que es O (n ^ 2) y Omega (n).

Además, los límites estrechos suelen ser más difíciles de calcular.

Ver también:

Halcón
fuente
66
Pero Big O no se corresponde necesariamente con el peor de los casos. Podría decir que quicksort se ejecuta en O (2 ^ n) y estar 100% correcto. Sería mucho más significativo si digo que el algoritmo X se ejecuta en Theta (N ^ 2) en lugar de O (N ^ 2).
tskuzzy
Además, los límites estrechos casi siempre se calculan al analizar algoritmos en lugar de solo un límite superior. Me pregunto por qué las personas no solo usan la notación theta mucho más expresiva cuando pueden.
tskuzzy
99
Te dije por qué la mayoría de los programadores no lo usan. Somos flojos y no necesitamos tanta precisión. Nadie te impide usar big theta si quieres. Adelante, hazlo. Su elección de algoritmo probablemente no se beneficiará tanto de ella. Nunca he oído hablar de un programador confundido por la gran notación O. A mí tampoco me resulta confuso en absoluto.
Falcon el
9

Una razón es que hay muchos casos en los que Θ simplemente no se conoce. Por ejemplo, la multiplicación de matrices es O (n ^ 2.376) pero no se conoce un límite apretado. Seguro, por lo que yo puedo decir, no es un apretado con destino a la multiplicación de matrices, pero no sabemos su valor.

MSalters
fuente
Pero esos serían los límites para el tiempo de ejecución de un problema, no un algoritmo particular. Si bien la multiplicación de matrices en general se puede resolver más rápido que el tiempo cúbico, el algoritmo ingenuo es Θ (n ^ 3) pase lo que pase.
tskuzzy
55
@tskuzzy, toma la clasificación rápida. No tiene un límite Theta, porque es O (n ^ 2) y Omega (n).
Peter Taylor