Complejidad de algoritmos

CAPÍTULO 7
ALGORITMOS Y SU COMPLEJIDAD

La tarea de programación está ligada al objetivo de obtener algoritmos que
resuelvan un problema con la mayor eficiencia posible; de hecho es sorprendente
comprobar las múltiples formas como podemos resolver un mismo problema y las
ventajas que conseguimos, en términos de eficiencia, al buscar soluciones
alternativas a las ya conocidas o consideradas comoevidentes.
El objetivo de este capítulo es doble: presentar la variedad de algoritmos existentes
para resolver una serie, necesariamente reducida, de problemas habituales de
distinta naturaleza y, en paralelo, formalizar la idea de “mayor eficiencia”,
estableciendo el concepto de complejidad algorítmica que desde el punto de vista
computacional es básico. Esto nos permite introducir determinadosconceptos
relacionados con los problemas que son potencialmente resolubles.

9030" OGFKFC"FG"NC"GHKEKGPEKC"["FG"NC
EQORNGLKFCF"CNIQTKVOKEC
Hasta ahora, el concepto de mayor eficiencia de un algoritmo frente a otro lo
hemos introducido de forma intuitiva, lo que no ha sido óbice para apostar por
algún método para obtener algoritmos más eficientes (p.e. divide y vencerás).
Para comparar y analizar laeficiencia de los algoritmos, éstos los consideraremos
escritos en un lenguaje de programación de alto nivel, pero aún empleando la
misma representación, establecer una medida precisa de la eficiencia de un
algoritmo no es fácil. En efecto, fijémonos en que una definición de eficiencia
podría ser el número de instrucciones que tiene el programa; sin embargo esto no
se correspondería, con elconcepto intuitivo que tenemos de eficiencia (según el
cual, el algoritmo más eficiente sería aquel que tardase menos tiempo en resolver el
problema sobre una misma máquina), dado que todas las instrucciones no utilizan
el mismo tiempo de procesador aun realizando la misma función (Ver ejemplo de
la Figura 7.1).
desde i:=1 hasta 10000

desde i:=1 hasta 10000
245

246

FUNDAMENTOS DE INFORMÁTICA YPROGRAMACIÓN

x ← i^2
x ← i*i
fin-desde
fin-desde
Fig. 7.1. El primer algoritmo es más costoso que el segundo, a pesar de hacer la
misma función, a causa de que la potencia es mucho más lenta que el producto.
Es más, el número de instrucciones puede reducirse sin que por ello disminuya el
número de instrucciones que realmente deben procesarse; así por ejemplo, un bucle
lo podemos programar tanto conuna estructura desde-hasta como con una
estructura mientras y aunque en este último caso se necesitan más instrucciones
(Ver Figura 7.2), realmente el tiempo de proceso es el mismo1.
desde i:=1 hasta 1000 i ← 1
acciones S
mientras i <= 1000
fin-desde
acciones S
i ← i+1
fin_mientras
Fig. 7.2. Los dos bucles implican los mismos cálculos, con independencia
del numero de instrucciones de susestructuras.
Por otra parte, como ya hemos hecho notar en capítulos anteriores, el propio
concepto de tipo de dato se utiliza, entre otras cosas, para emplear los métodos más
adecuados para realizar las operaciones entre los datos. Así, para un mismo
procesador, efectuar el producto de dos números es mucho más lento si estos
números son de tipo Real que si son de tipo Entero, aun siendo los mismos
números;sin embargo ambos casos son similares desde el punto de vista
algorítmico.
Todo lo anterior, unido a la dificultad de dar una medida de tiempo relativo ligada
a la ejecución de cada instrucción (sobre todo en lo que al acceso a periféricos se
refiere) hace que una definición precisa que se corresponda con el concepto
intuitivo de eficiencia tenga poco sentido. Cuestiones como las comentadasanteriormente, el bucle desde-hasta o el tipo de dato más adecuado, están ligadas a
cuestiones de implementación, más que al propio diseño del algoritmo, y pueden
optimizarse con suficiente práctica en la codificación de algoritmos. Sin embargo,
existen elementos ligados al propio diseño del algoritmo, que potencialmente son
mucho más impactantes sobre el tiempo de cálculo, que las consideraciones...