¿Por qué la notación O grande es más común si la notación theta grande nos da más información?

Lamentablemente, muchas personas están más familiarizadas con la notación O grande, y están menos familiarizadas con la notación Theta grande o con la notación Omega grande, por lo que usan la primera incluso cuando en realidad se debe usar una de las últimas.

Por ejemplo, puede ver fácilmente una declaración como “Quicksort se ejecuta en tiempo O (n log n), mientras que Bubblesort se ejecuta en O (n ^ 2)”. En realidad, Quicksort también se ejecuta en O (n ^ 2) (simplemente porque la notación O es un límite superior): la declaración se redactaría mejor como “Bubblesort se ejecuta en Omega (n ^ 2)” (o: en Theta (n ^ 2)).

Lo creas o no, en el curso de aprendizaje automático de Andrew Ng en Coursera (el curso más popular en Coursera), él (a sabiendas o no) comete el mismo error.

La notación theta grande le dice que el límite superior es estrecho , por lo que, de hecho, proporciona más información, pero esa información adicional puede ser difícil de obtener. Es decir, a menudo es mucho más fácil derivar un límite superior con el que estará satisfecho que encontrar el límite superior ajustado ( es decir, el mejor posible), que incluso podría depender de variables adicionales además de las del límite big-O fácil. Esto es especialmente probable para los algoritmos más complejos, como los que se encuentran en los trabajos de investigación.

La respuesta muy simple a esto es:

O grande se usa para la medida del peor de los casos y siempre estamos interesados ​​en la medida del peor de los casos , que muestra cómo funcionará el algoritmo en el peor de los casos, así es como comparamos dos algoritmos para encontrar cuál es mejor
Por ejemplo , la complejidad del tiempo en el peor de los casos de ordenación rápida es [matemática] O (n ^ 2) [/ matemática] y la complejidad del tiempo en el peor de los casos de ordenación por fusión es [matemática] O (n * logn) [/ matemática] y por eso fusionar tipo considerado como un mejor algoritmo, porque incluso en el peor de los casos funciona bien, mientras que si compara el caso promedio de ambos, ambos darán el mismo rendimiento que es [matemática] \ Theta [/ matemática] ([matemática] {n * logn} [ /matemáticas])

En la introducción de algoritmos, aprendemos que medimos el rendimiento del algoritmo con la entrada más grande posible y la medida del peor de los casos: puede consultar cualquier nota sobre esto

Creo que 1) inercia: la mayoría de las personas lo usan con más frecuencia, por lo que las personas tienden a usarlo con más frecuencia 2) porque incluso si demostramos el límite superior, incluso si sabemos que es el límite ajustado, para usar Theta todavía necesitaría pasar un momento escribiendo pruebas de que hay instancias [si estamos hablando del peor de los casos, para el caso promedio o alternativamente que la estimación del tiempo promedio de ejecución es exacta] para los cuales se cumple este límite superior. Esto a menudo podría ser solo dos oraciones fáciles (pero no siempre: para usar Theta, tendríamos que mostrar que el límite se cumple para todos menos un número finito de Ns, por lo que, por ejemplo, no debemos caer en una situación en la que no tenemos Probó que no es como si el algoritmo funciona en Theta (n ^ 2) aparte de si n es primo / n se divide por 15, etc., porque exactamente si n se divide por 15, entonces no hay posibilidad de construir una entrada en la que el algoritmo no terminará en Theta (n)), pero aún así dos oraciones necesitaríamos escribir en la prueba que no requiera decir “O”.