Una vez propuesto un algoritmo, surgen dos preguntas: ¿es correcto el algoritmo? —es decir, si en verdad encuentra una solución al problema— y ¿es eficiente? —o sea, en el supuesto de que el algoritmo realmente sea correcto, se requiere saber si facilitará el trabajo en cuanto a tiempo, dinero o algún otro aspecto.
Corrección. El algoritmo de Arcadio es correcto, pues para obtenerlo consideró una a una todas las posibilidades existentes. Después de completar la tabla 2, revisó una por una las ocho posibilidades para emplear la de mayor valor que, además, no sobrepasó la cantidad de dinero con la que contaba.
Complejidad. De esta forma se denomina el costo que genera el algoritmo, ya sea en tiempo, dinero o alguna otra medida. En el caso de Arcadio, implicó el tiempo empleado para calcular la tabla 2 y recorrer la última columna para encontrar la combinación de regalos óptima en la tabla 3. Supóngase que Arcadio demoró 10 segundos en llenar cada renglón de la tabla. La tabla 1 indica que son ocho renglones, lo que da como resultado un tiempo de 8 × 10 segundos = 80 segundos = 1 minuto, 20 segundos. En el supuesto de que la revisión de los últimos dos elementos de cada renglón en la tabla 3 le haya tomado cinco segundos, el total sería 8 × 5 = 40 segundos. En resumen, Arcadio resolvió el problema en dos minutos.
Concepto
Un algoritmo es correcto si para cualquier entrada válida al problema, produce una salida de acuerdo con la relación entrada/salida.
