Big-Oh notación. ¿Por qué? Principalmente porque es el primer tipo que aprende, y es muy popular en la literatura. Si la gente usa la notación Big-Oh de manera apropiada, transmite la información que generalmente desea transmitir. Si bien existen relaciones asintóticas más estrictas, Big-Oh se mantiene bien, ya que no es tan difícil de entender. Por lo general, la investigación en Ciencias de la Computación, como la investigación de Algoritmos, es atractiva para quienes están fuera de la estricta Ciencia de la Computación, y es útil utilizar la notación que es fácil de entender para aquellos que están fuera de ella. En algunos entornos, tiene más sentido usar cosas como la notación Big-Omega o la notación Big-Theta, cuando sea apropiado.
Otro beneficio adicional es que la notación Big-Oh es un límite superior asintótico, lo que significa que su comportamiento asintótico no es peor que eso. Una propiedad intrínseca de esto es que puedes establecer límites asintóticos aún estrechos (bajo cosas como límites Big-Theta) como notación Big-Oh y perder nada más que un símbolo mientras mantienes una audiencia más amplia.
Un malentendido común incluso de los graduados en informática es que Big-Oh siempre significa “peor de los casos”, esto no es cierto. El funcionamiento real del proceso es similar al siguiente:
- ¿Cómo escribiría una función que encuentre la entrada máxima n tal que f (n) <c en el tiempo O (lg n)?
- ¿Están algunas de las máquinas en 'On Computable Numbers' (A. Turing 1936) buggy?
- ¿Cuáles son algunos problemas realmente fáciles de explicar que en realidad son increíblemente difíciles de resolver?
- ¿Qué proyecto utilizando la teoría de grafos sería apropiado para una tesis de licenciatura de CS?
- ¿Qué métodos de análisis deberían usarse cuando el nivel de la variable dependiente es mucho mayor que el número de variable independiente?
- Elija su modelo de cálculo (generalmente este es el modelo RAM).
- Determine su tipo de análisis (peor, promedio, mejor).
- Formule el tiempo de ejecución del algoritmo como una función de crecimiento / complejidad basada en ese tipo de análisis.
- Determine el comportamiento asintótico de esa función de crecimiento.
- Bang, tiene la complejidad del tiempo.
Es decir, en el paso 4 puede usar diferentes tipos de notación asintótica.
¡Espero que esto ayude!
