¿Cuál es el significado del peor tiempo de ejecución de un algoritmo?

La notación Big O de un algoritmo proporciona un límite superior en su rendimiento. Describe el comportamiento limitante.

Definición formal: f (n) = O (g (n)) significa que existen constantes positivas c y k, de modo que 0 ≤ f (n) ≤ cg (n) para todo n ≥ k. Los valores de c y k deben ser fijos para la función f y no deben depender de n.

Significa que nunca se desempeñará peor que una determinada función.

Por ejemplo, n ^ 2 = O (n ^ 3). Cuando tiene una función ejecutándose en n ^ 2, ninguna constante u otra cosa puede hacer que crezca más rápido que n ^ 3 (a menos, por supuesto, que aumente su complejidad computacional, pero no lo haremos).

Consulte la página de Wikipedia para obtener más información.

Significa que, sobre todas las entradas posibles para ese algoritmo, ese tiempo de ejecución es el tiempo (asintóticamente) más largo.

Algunos algoritmos, por su propia naturaleza, se ejecutan (asintóticamente) más rápido en algunos algoritmos y más lento en otros, lo que significa que normalmente hay un tiempo promedio de ejecución de casos. El peor de los casos es el tiempo que el algoritmo toma la entrada más lenta para él.

Por ejemplo, el algoritmo BubbleSort ordena una lista de objetos al “burbujear” los objetos extraviados en su lugar, un espacio a la vez. Para ese algoritmo, el peor caso es cuando la lista se ordena en reversa y su tiempo de ejecución es O (n²).