Tiempo de ejecución
De cppreference.com
< cpp
Existen distintos modos de medir el tiempo de ejecución de un algoritmo. Dada una entrada de tamaño N, se los puede describir del siguiente modo.
| Nombre | Tiempo | Descripción | Formula | Ejemplo |
|---|---|---|---|---|
| factorial | lentisimo | su tiempo de ejecución es proporcional a N elevado a la N-ésima potencia | N! | Solución de fuerza bruta al problema del vendedor viajero |
| exponencial | lento | su tiempo de ejecución es proporcional a una constante elevada a la N-ésima potencia | KN | Solución de fuerza bruta para la resolución del cubo mágico o cubo de Rubik |
| polinomial | rápido | su tiempo de ejecución es proporcional a N elevado a una constante | NK | Ordenación por comparación (algoritmos de burbuja, inserción y selección) |
| logarítmico lineal | más rápido | su tiempo de ejecución esta entre el lineal y el polinomial | N * log(N) | Ordenación logaritmica lineal (quicksort, heapsort, mergesort) |
| lineal | aún más rápido | su tiempo de ejecución es proporcional a N | K * N | El recorrido de un arreglo |
| logarítmico | mucho más rápido | su tiempo de ejecución es proporcional al logaritmo de N | K * log(N) | Búsqueda binaria |
| constante | rapidisimo | siempre toma el mismo tiempo sin importar cuán grande sea N | K | Visualización de el elemento i-ésimo en un arreglo |
[editar]Analisis de Complejidad
Una operación puede tener diversos tiempo de ejecución/complejidad para distintos órdenes o conjuntos de datos de entrada. Estos son los diferentes métodos para analisis de complejidad:
| Nombre | Descripción | Ejemplo |
|---|---|---|
| mejor caso | Es es el caso en el que la operación se ejecuta tan rapido como es posible | La ordenación por burbuja tiene una complejidad de tiempo de mejor caso N |
| caso promedio | Es el caso donde la operación se ejecuta en un periodo de tiempo comparable a la mayoría de los casos posibles | El algoritmo quicksort tiene un tiempo de complejidad promedio de N * log(N) |
| peor caso | Es donde la operación se ejeucta lo mas lento posible | El algoritmo quicksort tiene un tiempo de complejidad en el peor de los casos de N2 |
| peor caso amortizado | Seria el promedio de el peor caso sobre un conjunto infinito de datos de entrada | vector::push_back() tiene un tiempo de complejidad amortizado en el peor de sus casos de K (tiempo constante) |
La elección de el mejor algoritmo depende de que casos se espera que la aplicación encuentre. Por ejemplo, una aplicación que deba protegerse a si misma de entradas maliciosas siempre evitara malas implementaciones de quickort que tiene un peor caso de complejidad de N2 aun cuando en su caso promedio mas rapido es mejor comparado con los otros algoritmos de ordenación.
