La complejidad de los algoritmos

UNAMBA
La complejidad de los algoritmos
(Caso práctico) Hace unos años presenciamos una discusión entre dos programadores sobre la “eficiencia de los programas“. Ellos discutían sobre la manera deespecificar el problema en la herramienta CASE que utilizaban, para que el programa generado fuera más “eficiente“. La discusión era acalorada y tenían visiones muy diferentes del asunto (al noconocer ni de cerca la herramienta en cuestión, no entendiamos ni media palabra de sus argumentos). Hasta que en un momento no pudimos contenernos y decidimos meter el dedo en el ventilador: A ver, unapregunta, ¿cuándo un programa es más eficiente que otro? – les preguntamos. Para nuestro asombro (aunque debería haberlo intuido), ambos respondieron al unísono: ¡Cuando es más corto!. No soñaría por uninstante que la mayoría de los programadores viven en tal ignorancia, pero sin embargo muchos no tienen demasiada claridad acerca de este asunto. Más aún, ni siquiera son conscientes de la enormediferencia que puede haber, a la hora de la ejecución, entre dos programas equivalentes pero de diferente complejidad temporal. Pensando en esto, recordamos un ejemplo utilizado por dos profes en unartículo llamado “La perplejidad como recurso didáctico“. Este ejemplo muestra cómo un cambio aparentemente sutil en un algoritmo puede impactar tremendamente en el rendimiento del programa resultante.

Elproblema
Supongamos que tenemos que escribir un programa para calcular potencias naturales de 2. Para ello podemos usar las operaciones aritméticas de suma y producto. Una solución posible seríacalcular:
 

20 = 1 2n = 2 * 2n – 1, para n > 0

Una alternativa sería considerar el caso “n > 0″ de forma diferente: sumando dos veces 2n – 1 en vez de multiplicando por 2. Esto es:
 

20 =1 2n = 2n – 1 + 2n – 1, para n > 0

Puede verse claramente que ambas soluciones son matemáticamente equivalentes. A continuación, el código en lenguaje pascal de las dos soluciones (pow1 y pow2,...