¿Hay una diferencia entre la declaración "El peor tiempo de ejecución de un algoritmo A" y "El tiempo de ejecución de un algoritmo A es O (n)"?
Lo que creo que "no hay diferencia" porque, en el peor de los casos, es el tiempo máximo de ejecución que puede tomar la función, O (n) significa que la función está "limitada por". Ambos dan el mismo significado.
Espero que mi lógica sea correcta.
Respuestas
7 para la respuesta № 1Hay diferencia
Un algoritmo es O (f) no es preciso: debe decir que un alirthnm es O (f) en su mejor / peor / último caso. Se puede decir que es O (f) cuando mejor, peor y promedio son iguales, pero eso no es tan común.
1 para la respuesta № 2
Estoy de acuerdo con tu sentimiento, pero hay cosas comunes.algoritmos (quicksort, por ejemplo) que tienen un tiempo esperado mucho mejor que en el peor de los casos. Podría decir que la ordenación rápida es O (N ^ 2) en el peor de los casos, pero aún así espera que sea O (N * log N) casi siempre (al menos para una buena implementación).
También se complica con algoritmos queHan amortizado el comportamiento. Podría obtener O (N) u O (registro N) para una operación en particular, pero muchas operaciones seguidas siempre serán O (1) en el sentido amortizado. Los árboles de separación y los árboles de dedos son buenos ejemplos en esta categoría.
1 para la respuesta № 3
El tiempo de ejecución como medida absoluta suele ser menos importante que Cómo aumenta ese tiempo cuando añades más datos. Por ejemplo, un algoritmo que siempre toma 5.Se dice que los segundos para procesar 100 elementos, 10 segundos para procesar 200 elementos, etc., son O (N), ya que el tiempo de ejecución aumenta linealmente con el tamaño del conjunto de datos. Si un segundo algoritmo tomó 5 * 5 = 25 segundos para procesar esos 200 elementos, podría clasificarse como O (N ^ 2). No hay "tiempo máximo de ejecución" aquí, ya que el tiempo de ejecución siempre aumenta cuando le arrojas más datos.
De hecho, la O grande es un límite superior, por lo que podríadigamos que el primer algoritmo también fue O (N ^ 2) (si N es un límite superior, N * N es mayor y, por lo tanto, también un límite superior, aunque uno más flexible). La notación común para denotar otros límites incluye Ω (omega, límite inferior) y Θ (theta, límite inferior y superior simultáneos).
Algunos algoritmos (por ejemplo, Quicksort) muestran un comportamiento diferente dependiendo de los datos que se le suministran; por lo tanto, el peor de los casos es O (N ^ 2), aunque generalmente se comporta como si fuera O (N log N).
0 para la respuesta № 4
Hay una gran diferencia entre esas cuerdasde palabras. "El peor tiempo de ejecución de un algoritmo A" es una cláusula de nombre, no hace ninguna declaración. "El tiempo de ejecución del algoritmo A es O (n)" es una oración que nos dice algo acerca de A.