4.2. Análisis de tiempos de ejecución.
El orden de complejidad depende del número de candidatos, de las funciones básicas a utilizar, del número de elementos de la solución.
N: número de elementos de C. M: número de elementos de una solución.
Repetir, como máximo N veces y como mínimo M:
- Comprobar si el valor actual es solución: f(M). Normalmente O(1) ó O(M).
- Selección de un elemento entre los candidatos: g(N). Entre O(1) y O(N).
- La función factible es parecida a solución, pero con una solución parcial h(M).
- La unión de un nuevo elemento a la solución puede requerir otras operaciones de cálculo, j(N, M).
Tiempo de ejecución genérico: t(N,M)?O(N*(f(M)+g(N)+h(M))+M*j(N, M))
Ejemplos:
- Algoritmos de Dijkstra, Prim y Kruskal: se ordenan los candidatos y se escogen de forma ordenada: O(a·log n).
- Devolución de monedas: podemos encontrar el siguiente elemento en un tiempo constante (ordenando las monedas): O(N).
En la práctica los algoritmos voraces suelen ser bastante rápidos, encontrándose dentro de órdenes de complejidad polinomiales.