En informática , los casos mejores , peores y 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 u otro recurso. El mejor caso 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 computación en tiempo real , el tiempo de ejecución del peor de los casos es a menudo de particular 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 medio y el rendimiento en el peor de los casos son los más utilizados en el análisis de algoritmos. El desempeño en el mejor de los casos se encuentra menos ampliamente , 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 resultado de una epidemia planificada, la temperatura del peor de los casos a la que está expuesto un elemento de circuito electrónico, etc. Cuando se utilizan componentes de tolerancia especificada , los dispositivos deben diseñarse para funcionar correctamente con el peor -Caso de combinación 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 caso: la mayoría de las empresas académicas y comerciales están más interesadas en mejorar la complejidad del caso medio 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 soluciones de codificación rígida para un conjunto finito de entradas, lo que hace que la medida casi carezca de sentido. [1]
Rendimiento en el peor de los casos frente al promedio
El análisis de desempeño en el peor de los casos y el análisis de desempeño en el caso promedio tienen algunas similitudes, pero en la práctica generalmente requieren diferentes herramientas y enfoques.
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). De manera similar, incluso cuando es posible una descripción sensata de un "caso promedio" particular (que probablemente sólo será aplicable para algunos usos del algoritmo), tienden a resultar en un análisis de ecuaciones más difícil. [2]
El análisis del peor de los casos proporciona un análisis seguro (el peor de los casos nunca se subestima), pero uno que puede ser demasiado pesimista , ya que puede que no haya una entrada (realista) que dé 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 acerca más al valor real pero puede ser optimista (quizás con alguna probabilidad de falla conocida baja) 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 caso medio y el peor de los casos se llama análisis suavizado .
Cuando se analizan algoritmos que a menudo tardan un poco en completarse, pero que periódicamente requieren mucho más tiempo, se puede utilizar el análisis amortizado para determinar el tiempo de ejecución del peor de los casos en una serie (posiblemente infinita) de operaciones . Este costo amortizado en el peor de los casos puede estar mucho más cerca del costo promedio del caso, al mismo tiempo que proporciona un límite superior garantizado en el tiempo de ejecución.
El análisis del peor de los casos está relacionado con la complejidad del peor de los casos . [3]
Consecuencias practicas
Muchos algoritmos con un 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 los casos típicos de un problema criptográfico sean difíciles. Aquí, métodos como la autorreducción aleatoria se pueden utilizar 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 en el peor de los casos muy deficientes, pero una tabla hash bien escrita y de tamaño suficiente nunca dará estadísticamente 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 de
Ordenar algoritmos
Algoritmo | Estructura de datos | Complejidad de tiempo: mejor | Complejidad de tiempo: promedio | Complejidad del tiempo: peor | Complejidad espacial: peor |
---|---|---|---|---|---|
Ordenación rápida | Formación | O ( n log ( n )) | O ( n log ( n )) | O ( n 2 ) | O ( n ) |
Combinar ordenación | Formación | O ( n log ( n )) | O ( n log ( n )) | O ( n log ( n )) | O ( n ) |
Tipo de pila | Formación | O ( n log ( n )) | O ( n log ( n )) | O ( n log ( n )) | O (1) |
Orden suave | Formación | O ( n ) | O ( n log ( n )) | O ( n log ( n )) | O (1) |
Ordenamiento de burbuja | Formación | O ( n ) | O ( n 2 ) | O ( n 2 ) | O (1) |
Tipo de inserción | Formación | O ( n ) | O ( n 2 ) | O ( n 2 ) | O (1) |
Orden de selección | Formación | O ( n 2 ) | O ( n 2 ) | O ( n 2 ) | O (1) |
Tipo bogo | Formación | O ( n ) | O ( n n !) | O (∞) | O (1) |
- Orden de inserción aplicado a una lista de n elementos, que se supone que son todos diferentes e inicialmente en orden aleatorio. En promedio, la mitad de los elementos de una lista A 1 ... A j son menores que el elemento A j +1 , y la mitad son mayores. Por lo tanto, el algoritmo compara el elemento ( j + 1) ésimo que se insertará en promedio con la mitad de la sublista ya ordenada, por lo que t j = j / 2. Al calcular el tiempo de ejecución del caso promedio resultante, se obtiene una función cuadrática del tamaño de entrada, al igual que el tiempo de ejecución del peor de los casos.
- Quicksort aplicado a una lista de n elementos, nuevamente asumidos como todos diferentes e inicialmente en orden aleatorio. Este popular algoritmo de clasificación tiene un rendimiento de caso promedio de O ( n log ( n )), lo que contribuye a convertirlo en un algoritmo muy rápido en la práctica. Pero dada una entrada en el peor de los casos, su rendimiento se degrada a O ( n 2 ). Además, cuando se implementa con la política de "primero el más corto", la complejidad del espacio en el peor de los casos está limitada por O (log ( n )).
- Heapsort tiene tiempo O (n) cuando todos los elementos son iguales. Heapify toma O (n) tiempo y luego eliminar elementos del montón es O (1) tiempo para cada uno de los n elementos. El tiempo de ejecución aumenta a O (nlog (n)) si todos los elementos deben ser distintos.
- Bogosort tiene O (n) tiempo cuando los elementos se ordenan en la primera iteración. En cada iteración, todos los elementos se verifican si están en orden. ¡No hay! posibles permutaciones; con un generador de números aleatorios equilibrado, casi cada permutación de la matriz se obtiene en n! iteraciones. Las computadoras tienen memoria limitada, por lo que los números generados tienen un ciclo; puede que no sea posible alcanzar cada permutación. En el peor de los casos, esto conduce a un tiempo O (∞), un bucle infinito.
Estructuras de datos
Estructura de datos | Complejidad del tiempo | Complejidad espacial | |||||||
---|---|---|---|---|---|---|---|---|---|
Promedio: indexación | Promedio: búsqueda | Promedio: inserción | Promedio: eliminación | Lo peor: indexación | Lo peor: búsqueda | Lo peor: Inserción | Lo peor: eliminación | Peor | |
Matriz básica | O (1) | O ( n ) | - | - | O (1) | O ( n ) | - | - | O ( n ) |
Matriz dinámica | O (1) | O ( n ) | O ( n ) | - | O (1) | O ( n ) | O ( n ) | - | O ( n ) |
Lista individualmente vinculada | O ( n ) | O ( n ) | O (1) | O (1) | O ( n ) | O ( n ) | O (1) | O (1) | O ( n ) |
Lista doblemente enlazada | O ( n ) | O ( n ) | O (1) | O (1) | O ( n ) | O ( n ) | O (1) | O (1) | O ( n ) |
Tabla de picadillo | - | O (1) | O (1) | O (1) | - | O ( n ) | O ( n ) | O ( n ) | O ( n ) |
Árbol de búsqueda binaria | - | O (registro ( n )) | O (registro ( n )) | O (registro ( n )) | - | O ( n ) | O ( n ) | O ( n ) | O ( n ) |
Árbol B | - | O (registro ( n )) | O (registro ( n )) | O (registro ( n )) | - | O (registro ( n )) | O (registro ( n )) | O (registro ( n )) | O ( n ) |
Árbol rojo-negro | - | O (registro ( n )) | O (registro ( n )) | O (registro ( n )) | - | O (registro ( n )) | O (registro ( n )) | O (registro ( n )) | O ( n ) |
Árbol AVL | - | O (registro ( n )) | O (registro ( n )) | O (registro ( n )) | - | O (registro ( n )) | O (registro ( n )) | O (registro ( n )) | O ( n ) |
- Búsqueda lineal en una lista de n elementos. En el peor de los casos, 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, asumiendo que el valor buscado está en la lista y cada elemento de la lista tiene la misma probabilidad de ser el valor buscado, la búsqueda solo visita n / 2 elementos.
Ver también
- Algoritmo de clasificación : un área donde hay una gran cantidad de análisis de rendimiento de varios algoritmos.
- Estructura de datos de búsqueda : cualquier estructura de datos que permita la recuperación eficiente de elementos específicos.
- Análisis de circuito en el peor de los casos
- Análisis suavizado
- Elemento finito de intervalo
- Notación Big O
Referencias
- ^ Introducción a los algoritmos (Cormen, Leiserson, Rivest y Stein) 2001, Capítulo 2 "Introducción". En la complejidad del mejor de los casos , proporciona el límite inferior del tiempo de ejecución del algoritmo de cualquier instancia de entrada.
- ^ Spielman, Daniel ; Teng, Shang-Hua (2009), "Análisis suavizado: un intento de explicar el comportamiento de los algoritmos en la práctica" (PDF) , Comunicaciones del ACM , ACM, 52 (10): 76-84, doi : 10.1145 / 1562764.1562785
- ^ "Complejidad en el peor de los casos" (PDF) . Archivado (PDF) desde el original el 21 de julio de 2011 . Consultado el 30 de noviembre de 2008 .