4.3.2. Planificación de tareas.
Ejemplo: n=6
g = (20, 15, 10, 7, 5, 3)
d = ( 3, 1, 1, 3, 1, 3)
Es posible demostrar que este algoritmo obtiene la solución óptima. Idea: suponer una solución óptima y comprobar que tiene el mismo beneficio que la calculada por el algoritmo.
Orden de complejidad del algoritmo, suponiendo n tareas:
- Primero, ordenar las tareas por orden creciente de plazo: O(n·log n)
- Repetir para i desde 1 hasta n:
- Elegir el próximo candidato: O(1).
- Comprobar si la nueva planificación es factible, y añadirlo a la solución en caso afirmativo: O(i) en el peor caso.
- En total, el algoritmo es de O(n2).