algoritmo

Capítulo 1
LA COMPLEJIDAD DE LOS ALGORITMOS

1.1 INTRODUCCIÓN
En un sentido amplio, dado un problema y un dispositivo donde resolverlo, es
necesario proporcionar un método preciso que lo resuelva, adecuado al dispositivo.
A tal método lo denominamos algoritmo.
En el presente texto nos vamos a centrar en dos aspectos muy importantes de los
algoritmos, como son su diseño y el estudio de sueficiencia.
El primero se refiere a la búsqueda de métodos o procedimientos, secuencias
finitas de instrucciones adecuadas al dispositivo que disponemos, que permitan
resolver el problema. Por otra parte, el segundo nos permite medir de alguna forma
el coste (en tiempo y recursos) que consume un algoritmo para encontrar la
solución y nos ofrece la posibilidad de comparar distintos algoritmosque resuelven
un mismo problema.
Este capítulo está dedicado al segundo de estos aspectos: la eficiencia. En
cuanto a las técnicas de diseño, que corresponden a los patrones fundamentales
sobre los que se construyen los algoritmos que resuelven un gran número de
problemas, se estudiarán en los siguientes capítulos.
1.2 EFICIENCIA Y COMPLEJIDAD
Una vez dispongamos de un algoritmo quefunciona correctamente, es necesario
definir criterios para medir su rendimiento o comportamiento. Estos criterios se
centran principalmente en su simplicidad y en el uso eficiente de los recursos.
A menudo se piensa que un algoritmo sencillo no es muy eficiente. Sin
embargo, la sencillez es una característica muy interesante a la hora de diseñar un
algoritmo, pues facilita su verificación, elestudio de su eficiencia y su
mantenimiento. De ahí que muchas veces prime la simplicidad y legibilidad del
código frente a alternativas más crípticas y eficientes del algoritmo. Este hecho se
pondrá de manifiesto en varios de los ejemplos mostrados a lo largo de este libro,
en donde profundizaremos más en este compromiso.
Respecto al uso eficiente de los recursos, éste suele medirse en función dedos
parámetros: el espacio, es decir, memoria que utiliza, y el tiempo, lo que tarda en
ejecutarse. Ambos representan los costes que supone encontrar la solución al
problema planteado mediante un algoritmo. Dichos parámetros van a servir además
para comparar algoritmos entre sí, permitiendo determinar el más adecuado de

2

TÉCNICAS DE DISEÑO DE ALGORITMOS

entre varios que solucionanun mismo problema. En este capítulo nos centraremos
solamente en la eficiencia temporal.
El tiempo de ejecución de un algoritmo va a depender de diversos factores
como son: los datos de entrada que le suministremos, la calidad del código
generado por el compilador para crear el programa objeto, la naturaleza y rapidez
de las instrucciones máquina del procesador concreto que ejecute elprograma, y la
complejidad intrínseca del algoritmo. Hay dos estudios posibles sobre el tiempo:
1. Uno que proporciona una medida teórica (a priori), que consiste en obtener una
función que acote (por arriba o por abajo) el tiempo de ejecución del algoritmo
para unos valores de entrada dados.
2. Y otro que ofrece una medida real (a posteriori), consistente en medir el tiempo
de ejecución delalgoritmo para unos valores de entrada dados y en un
ordenador concreto.
Ambas medidas son importantes puesto que, si bien la primera nos ofrece
estimaciones del comportamiento de los algoritmos de forma independiente del
ordenador en donde serán implementados y sin necesidad de ejecutarlos, la
segunda representa las medidas reales del comportamiento del algoritmo. Estas
medidas son funcionestemporales de los datos de entrada.
Entendemos por tamaño de la entrada el número de componentes sobre los que
se va a ejecutar el algoritmo. Por ejemplo, la dimensión del vector a ordenar o el
tamaño de las matrices a multiplicar.
La unidad de tiempo a la que debe hacer referencia estas medidas de eficiencia
no puede ser expresada en segundos o en otra unidad de tiempo concreta, pues no...