Caso mejor, peor y promedio
En informática, mejor, peor y casos promedio de un algoritmo dado expresan cuál es el uso de recursos al menos , como máximo y en promedio, respectivamente. Por lo general, el recurso que se considera es el tiempo de ejecución, es decir, la complejidad del tiempo, pero también podría ser la memoria o algún otro recurso. El mejor de los casos es la función que realiza el número mínimo de pasos en los datos de entrada de n elementos. El peor de los casos es la función que realiza el número máximo de pasos en datos de entrada de tamaño n. El caso promedio es la función que realiza un número promedio de pasos en los datos de entrada de n elementos.
En la informática en tiempo real, el tiempo de ejecución en el peor de los casos suele ser motivo de especial preocupación, ya que es importante saber cuánto tiempo podría ser necesario en el peor de los casos para garantizar que el algoritmo siempre terminar a tiempo.
El rendimiento promedio y el rendimiento en el peor de los casos son los más utilizados en el análisis de algoritmos. Menos ampliamente encontrado es el rendimiento del mejor de los casos, pero tiene usos: por ejemplo, cuando se conocen los mejores casos de tareas individuales, se pueden usar para mejorar la precisión de un análisis general del peor de los casos. Los informáticos utilizan técnicas de análisis probabilístico, especialmente el valor esperado, para determinar los tiempos de ejecución esperados.
Los términos se utilizan en otros contextos; por ejemplo, el peor y el mejor de los casos de una epidemia, la temperatura del peor de los casos a la que se expone un elemento de un circuito electrónico, etc. de tolerancias y condiciones externas.
Rendimiento en el mejor de los casos para el algoritmo
El término rendimiento en el mejor de los casos se utiliza en informática para describir el comportamiento de un algoritmo en condiciones óptimas. Por ejemplo, el mejor caso para una búsqueda lineal simple en una lista ocurre cuando el elemento deseado es el primer elemento de la lista.
El desarrollo y la elección de algoritmos rara vez se basan en el rendimiento del mejor de los casos: la mayoría de las empresas académicas y comerciales están más interesadas en mejorar la complejidad del caso promedio y el rendimiento en el peor de los casos. Los algoritmos también pueden modificarse trivialmente para tener un buen tiempo de ejecución en el mejor de los casos mediante la codificación de soluciones para un conjunto finito de entradas, lo que hace que la medida casi no tenga sentido.
Desempeño en el peor de los casos, amortizado y en el caso promedio
El análisis de rendimiento en el peor de los casos y el análisis de rendimiento en el caso promedio tienen algunas similitudes, pero en la práctica, por lo general, requieren herramientas y enfoques diferentes.
Determinar qué significa entrada típica es difícil y, a menudo, esa entrada promedio tiene propiedades que dificultan la caracterización matemática (considere, por ejemplo, algoritmos que están diseñados para operar en cadenas de texto). Del mismo modo, incluso cuando una descripción sensata de un "caso promedio" (que probablemente solo sea aplicable para algunos usos del algoritmo) es posible, tienden a resultar en análisis de ecuaciones más difíciles.
El análisis del peor de los casos proporciona un análisis seguro (nunca se subestima el peor de los casos), pero uno que puede ser demasiado pesimista, ya que puede no haber (realista) entrada que tomaría tantos pasos.
En algunas situaciones puede ser necesario utilizar un análisis pesimista para garantizar la seguridad. Sin embargo, a menudo, un análisis pesimista puede ser demasiado pesimista, por lo que un análisis que se acerque más al valor real pero que sea optimista (quizás con alguna baja probabilidad conocida de falla) puede ser un enfoque mucho más práctico. Un enfoque moderno en la teoría académica para cerrar la brecha entre el análisis del peor caso y el caso promedio se llama análisis suavizado.
Al analizar algoritmos que a menudo tardan poco en completarse, pero que periódicamente requieren mucho más tiempo, el análisis amortizado se puede utilizar para determinar el tiempo de ejecución en el peor de los casos en una serie de operaciones (posiblemente infinita). Este costo amortizado puede estar mucho más cerca del costo promedio, al mismo tiempo que proporciona un límite superior garantizado en el tiempo de ejecución. Entonces, p. Los algoritmos en línea se basan con frecuencia en análisis amortizados.
El análisis del peor de los casos está relacionado con la complejidad del peor de los casos.
Consecuencias prácticas
Muchos algoritmos con mal desempeño en el peor de los casos tienen un buen desempeño en el caso promedio. Para los problemas que queremos resolver, esto es algo bueno: podemos esperar que las instancias particulares que nos interesan sean promedio. Para la criptografía, esto es muy malo: queremos que las instancias típicas de un problema criptográfico sean difíciles. Aquí se pueden usar métodos como la autorreducibilidad aleatoria para algunos problemas específicos para mostrar que el peor de los casos no es más difícil que el caso promedio o, de manera equivalente, que el caso promedio no es más fácil que el peor de los casos.
Por otro lado, algunas estructuras de datos como las tablas hash tienen comportamientos muy pobres en el peor de los casos, pero una tabla hash bien escrita de tamaño suficiente estadísticamente nunca dará el peor de los casos; el número medio de operaciones realizadas sigue una curva de caída exponencial, por lo que el tiempo de ejecución de una operación está acotado estadísticamente.
Ejemplos
Algoritmos de clasificación
| Algoritm | Estructura de datos | Complejidad del tiempo: Mejor | Complejidad del tiempo: Promedio | Complejidad del tiempo: peor | Complicidad espacial: peor |
|---|---|---|---|---|---|
| Tipo rápido | Array | O...n log(n) | O...n log(n) | O...n2) | O...n) |
| Merge tipo | Array | O...n log(n) | O...n log(n) | O...n log(n) | O...n) |
| Un montón | Array | O...n log(n) | O...n log(n) | O...n log(n) | O(1) |
| Smooth tipo | Array | O...n) | O...n log(n) | O...n log(n) | O(1) |
| Bubble tipo | Array | O...n) | O...n2) | O...n2) | O(1) |
| Tipo de inserción | Array | O...n) | O...n2) | O...n2) | O(1) |
| Tipo de selección | Array | O...n2) | O...n2) | O...n2) | O(1) |
| Bogo especie | Array | O...n) | O...n n! | O(∞) | O(1) |
- Tipo de inserción aplicado a una lista n elementos, considerados todos diferentes e inicialmente en orden aleatorio. En promedio, la mitad de los elementos de una lista A1... Aj son menos que elemento Aj+ 1, y la mitad son mayores. Por lo tanto, el algoritmo compara el (j+ 1)T elemento a insertar en el promedio con la mitad de la sublista ya clasificada, por lo que tj = j/2. Trabajar en el tiempo de ejecución promedio resultante produce una función cuadrática del tamaño de la entrada, al igual que el peor de los casos.
- Quicksort aplicado a una lista de n elementos, de nuevo suponían ser todos diferentes e inicialmente en orden aleatorio. Este algoritmo de clasificación popular tiene un rendimiento promedio de O(nlog(n)), que contribuye a convertirlo en un algoritmo muy rápido en la práctica. Pero dada una entrada peor, su rendimiento se degrada a O(n2). Además, cuando se implementa con la política "primera" más corta, la peor complejidad espacial está ligada por O(log(n)).
- Heapsort tiene tiempo O(n) cuando todos los elementos son iguales. Heapify toma tiempo O(n) y luego quitar elementos del montón es tiempo O(1) para cada uno de los elementos n. El tiempo de ejecución crece a O(nlog(n)) si todos los elementos deben ser distintos.
- Bogosort tiene tiempo O(n) cuando los elementos se clasifican en la primera iteración. En cada iteración se comprueban todos los elementos si están en orden. Hay n! permutaciones posibles; con un generador de número aleatorio equilibrado, casi cada permutación de la matriz se rinde en n!! iteraciones. Las computadoras tienen memoria limitada, por lo que el ciclo de números generados; podría no ser posible alcanzar cada permutación. En el peor de los casos esto conduce al tiempo O(∞), un bucle infinito.
Estructuras de datos
| Estructura de datos | Complejo de tiempo | Competencia espacial | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Avg: Indexing | Avg: Search | Avg: Insertion | Avg: Deletion | Lo peor: Indización | Lo peor: Búsqueda | peor: inserción | Lo peor: eliminación | peor | |
| Conjunto básico | O(1) | O...n) | O...n) | O...n) | O(1) | O...n) | O...n) | O...n) | O...n) |
| matriz dinámica | O(1) | O...n) | O...n) | — | O(1) | O...n) | O...n) | — | O...n) |
| Stack | O...n) | O...n) | O(1) | O(1) | O...n) | O...n) | O(1) | O(1) | O...n) |
| Queue | O...n) | O...n) | O(1) | O(1) | O...n) | O...n) | O(1) | O(1) | O...n) |
| Lista de contactos | O...n) | O...n) | O(1) | O(1) | O...n) | O...n) | O(1) | O(1) | O...n) |
| Lista doblemente vinculada | O...n) | O...n) | O(1) | O(1) | O...n) | O...n) | O(1) | O(1) | O...n) |
| Lista de candidatos | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O...n) | O...n) | O...n) | O...n) | O...nlog (n) |
| Hash table | — | O(1) | O(1) | O(1) | — | O...n) | O...n) | O...n) | O...n) |
| Árbol de búsqueda binario | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O...n) | O...n) | O...n) | O...n) | O...n) |
| Árbol cartesiano | — | O(log)n) | O(log)n) | O(log)n) | — | O...n) | O...n) | O...n) | O...n) |
| B-tree | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O...n) |
| Árbol rojo-negro | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O...n) |
| Splay árbol | — | O(log)n) | O(log)n) | O(log)n) | — | O(log)n) | O(log)n) | O(log)n) | O...n) |
| Árbol AVL | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O...n) |
| K-d tree | O(log)n) | O(log)n) | O(log)n) | O(log)n) | O...n) | O...n) | O...n) | O...n) | O...n) |
- Búsqueda lineal en una lista de n elementos. En el peor caso absoluto, la búsqueda debe visitar cada elemento una vez. Esto sucede cuando el valor que se busca es el último elemento de la lista, o no está en la lista. Sin embargo, en promedio, suponiendo que el valor buscado está en la lista y cada elemento de lista es igualmente probable que sea el valor buscado, las visitas de búsqueda sólo n/2 elementos.
Contenido relacionado
Macro (ciencias de la computación)
10BASE5
Red de área metropolitana