Complejidad Algoritmica

1. INTRODUCCIÓN.

Dos ideas cambiaron al mundo. En 1448 en la ciudad de Mainz, un orfebre llamado Johann Gutenberg descubrió el camino para imprimir libros colocando juntas dos piezas metálicas móviles. En este momento se inició la disipación de la edad obscura y el intelecto humano se liberaba, la ciencia y la tecnología había triunfado, con ello inició la fermentación de la semilla queculminó con la revolución industrial. Varios historiadores indican que nosotros se lo debemos a la tipografía. Imagine a un mundo en el cual sólo una elite podría leer estas líneas. Pero otros insisten que la llave del desarrollo no fue la tipografía, sino que fue la algorítmica.

Fig. 1.1. Johann Gutenberg (1398-1468)

En nuestros días, estamos acostumbrados a escribir números en notacióndecimal, es fácil de olvidad que Gutenberg para escribir 1448 era como MCDXLVIII. ¿Cómo se pueden sumar dos números romanos? Lo máximo que podría hacer Gutenberg era sumar números pequeños con los dedos de sus manos; para algo más complicado se tendría que consultar el ábaco.
El sistema decimal, inventado en la India alrededor del año 600 A. C. produjo una revolución en razonamiento cualitativo:usando sólo 10 símbolos, aún números de gran tamaño podrían escribirse sin ninguna complicación. Cualquier operación aritmética se puede realizar sin ninguna complicación. No obstante, estas ideas tardaron bastante tiempo en expandirse, debido a la ignorancia, tradiciones, distancia y la barrera del lenguaje. El medio de mayor influencia para permitir la transmisión de éstos conocimientos se realizópor medio de un libro, escrito por un árabe del siglo noveno que vivió en Bagdad. Al Khwarizmi. Él dio los métodos básicos para la suma, resta, multiplicación, división e inclusive para la raíz cuadrada y el cálculo de ∏. Los procedimientos fueron precisos, no ambiguos mecánicos, eficientes y correctos, fueron algoritmos, un término acuñado en honor al hombre sabio. El sistema decimal fue adoptadoen Europa varios siglos después.
Desde la aparición de la notación decimal en Europa se permitió que la tecnología, la ciencia, el comercio y la industria, y posteriormente el computo se desarrollaran plenamente. Científicos de todo el mundo desarrollaron cada vez algoritmos más complejos para todo tipo de problemas e investigaron novedosas aplicaciones que han cambiado al mundo en formaradical.

Fig. 1.2 Al Khwarizmi.
El trabajo de Al Khwarizmi se pudo establecer en Europa por el esfuerzo de un matemático italiano del siglo 13 conocido como Leonardo Fibonacci, quien descubrió el potencial del sistema posicional y trabajó bastante para el desarrollo y futura propagación.
Pero, hoy en día, Fibonacci es más conocido por la famosa secuencia de números:
0,1,1,2,3,5,8,13,21,38…Formalmente hablando, los números de Fibonacci Fn son generados por una regla simple:

Fn-1 + Fn-2 Si n > 1

Fn = 1 Si n = 1

0 Si n = 0


Fig. 1.3. Leonardo de Pisa (1170-1250)

No existe otra secuencia de números que haya sido estudiada en forma tan extensa, o aplicada a más campos del conocimiento: biología, demografía, arte,arquitectura, música, para nombrar algunos de los campos. Y junto con la potencia de dos, es en ciencias de la computación una de las secuencias favoritas.

En realidad, la secuencia de Fibonacci crece tan rápido como la potencia de dos: por ejemplo, F30 rebasa el millón, y la secuencia F100 tiene aproximadamente 21 dígitos de largo. En general, Fn ≈ 20.694n .

Peor, ¿Cuál es el valor exacto de F100o de F200 ? Fibonacci nunca supo la respuesta. Para saberlo, necesitamos un algoritmo para computar el n-ésimo número de Fibonacci.
Una idea es utilizar la definición recursiva de Fn . El pseudocódigo se muestra enseguida:

Función fib1(n)
Si n=0 retorna 0
Si n=1 retorna 1
Retorna fib1(n-1) + fib1(n-2)

Todas las veces que se tiene un algoritmo, existen preguntas que se deben de...