Page 107 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 107
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Por lo tanto,
Un algoritmo que procede a encontrar un recorrido óptimo haciendo uso de (1) y (2) requerirá 0 (n
2
2 ) veces para el cálculo de g (i, S) con |S| = k requiere k – 1 comparaciones para resolver (2). Esto
n
es mejor que la enumeración de todos los n diferentes recorridos para encontrar el mejor recorrido
(conocido como fuerza bruta). El inconveniente más grave de esta solución con programación di-
námica es el espacio requerido. El espacio necesario es (n2 ). Esto es demasiado grande incluso
n
para valores modestos de n.
101
