Mergesort tiempo de funcionamiento BigO

Question

libro de texto de Snape “antipático algoritmos para Wizards” afirma que el tiempo de ejecución de fusión especie es O (n ^ 4). ¿Es correcta esta afirmación?

Solución: Sí. Esta afirmación es técnicamente correcto, porque O (n ^ 4) sólo da una superior con destino a cuánto tiempo tarda el algoritmo. Sin embargo, es una respuesta desagradable poco útil, ya que el apretado unido es Θ(n log n).

No estoy muy comprensión de lo que la solución está declarando. ¿Cómo puede O (n ^ 4) ser correcto?

Answer 1

O grande notación es un límite superior en el peor de los casos para un tiempo de ejecución de algoritmo.

Desde O (n ^ 4) está por encima del tiempo en el peor caso de mergesort es técnicamente correcta, ya que proporciona una cota - es decir. Por fusión nunca tendrá un rendimiento peor que O (n ^ 4).

Sin embargo, es poco útil, porque una mejor expresión del tiempo de ejecución es O (n log n), que es el "más ajustado" con destino a merge sort

Answer 2

Big-O es un conjunto, que incluye todo lo que corre tan rápido como (foo) o más rápido. Poco-O es un conjunto de cosas que se ejecutan más rápido de lo estrictamente (foo). Si bien es correcto decir mergesort es O (n ^ 4) que no es muy útil, porque es Theta (n log n). Decir que mergesort es O (n ^ 4) es marginalmente más útil, porque poco-o notación nunca se utiliza para implicar gran-theta tiempo de ejecución.

Para complicar aún más las cosas, de orden O se utiliza a menudo cuando Big-theta sería más apropiado, porque la mayoría de los teclados no tienen una teta.