Capítulo 1 LA COMPLEJIDAD DE LOS ALGORITMOS - UMA

1 Cap tulo 1 LA COMPLEJIDAD DE LOS ALGORITMOS 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 su eficiencia. 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 ALGORITMOS que resuelven un mismo problema.

2 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. EFICIENCIA Y COMPLEJIDAD Una vez dispongamos de un algoritmo que funciona 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, el estudio de su eficiencia y su mantenimiento.

3 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 de dos 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 solucionan un mismo problema.

4 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 el programa, 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 del algoritmo para unos valores de entrada dados y en un ordenador concreto.

5 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 funciones temporales 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 existe un ordenador est ndar al que puedan hacer referencia todas las medidas.

6 Denotaremos por T(n) el tiempo de ejecuci n de un algoritmo para una entrada de tama o n. Te ricamente T(n) debe indicar el n mero de instrucciones ejecutadas por un ordenador idealizado. Debemos buscar por tanto medidas simples y abstractas, independientes del ordenador a utilizar. Para ello es necesario acotar de alguna forma la diferencia que se puede producir entre distintas implementaciones de un mismo algoritmo, ya sea del mismo c digo ejecutado por dos m quinas de distinta velocidad, como de dos c digos que implementen el mismo m todo. Esta diferencia es la que acota el siguiente principio: Principio de Invarianza Dado un algoritmo y dos implementaciones suyas I1 e I2, que tardan T1(n) y T2(n) segundos respectivamente, el Principio de Invarianza afirma que existe una constante real c > 0 y un n mero natural n0 tales que para todo n n0 se verifica que T1(n) cT2(n).

7 Es decir, el tiempo de ejecuci n de dos implementaciones distintas de un algoritmo dado no va a diferir m s que en una constante multiplicativa. LA COMPLEJIDAD DE LOS ALGORITMOS 3 Con esto podemos definir sin problemas que un algoritmo tarda un tiempo del orden de T(n) si existen una constante real c > 0 y una implementaci n I del algoritmo que tarda menos que cT(n), para todo n tama o de la entrada. Dos factores a tener muy en cuenta son la constante multiplicativa y el n0 para los que se verifican las condiciones, pues si bien a priori un algoritmo de orden cuadr tico es mejor que uno de orden c bico, en el caso de tener dos ALGORITMOS cuyos tiempos de ejecuci n son 106n2 y 5n3 el primero s lo ser mejor que el segundo para tama os de la entrada superiores a Tambi n es importante hacer notar que el comportamiento de un algoritmo puede cambiar notablemente para diferentes entradas (por ejemplo, lo ordenados que se encuentren ya los datos a ordenar).

8 De hecho, para muchos programas el tiempo de ejecuci n es en realidad una funci n de la entrada espec fica, y no s lo del tama o de sta. As suelen estudiarse tres casos para un mismo algoritmo: caso peor, caso mejor y caso medio. El caso mejor corresponde a la traza (secuencia de sentencias) del algoritmo que realiza menos instrucciones. An logamente, el caso peor corresponde a la traza del algoritmo que realiza m s instrucciones. Respecto al caso medio, corresponde a la traza del algoritmo que realiza un n mero de instrucciones igual a la esperanza matem tica de la variable aleatoria definida por todas las posibles trazas del algoritmo para un tama o de la entrada dado, con las probabilidades de que stas ocurran para esa entrada.

9 Es muy importante destacar que esos casos corresponden a un tama o de la entrada dado, puesto que es un error com n confundir el caso mejor con el que menos instrucciones realiza en cualquier caso, y por lo tanto contabilizar las instrucciones que hace para n = 1. A la hora de medir el tiempo, siempre lo haremos en funci n del n mero de operaciones elementales que realiza dicho algoritmo, entendiendo por operaciones elementales (en adelante OE) aquellas que el ordenador realiza en tiempo acotado por una constante. As , consideraremos OE las operaciones aritm ticas b sicas, asignaciones a variables de tipo predefinido por el compilador, los saltos (llamadas a funciones y procedimientos, retorno desde ellos, etc.)

10 , las comparaciones l gicas y el acceso a estructuras indexadas b sicas, como son los vectores y matrices. Cada una de ellas contabilizar como 1 OE. Resumiendo, el tiempo de ejecuci n de un algoritmo va a ser una funci n que mide el n mero de operaciones elementales que realiza el algoritmo para un tama o de entrada dado. En general, es posible realizar el estudio de la COMPLEJIDAD de un algoritmo s lo en base a un conjunto reducido de sentencias, aquellas que caracterizan que el algoritmo sea lento o r pido en el sentido que nos interesa. Tambi n es posible distinguir entre los tiempos de ejecuci n de las diferentes operaciones elementales, lo cual es necesario a veces por las caracter sticas espec ficas del ordenador (por ejemplo, se podr a considerar que las operaciones + y presentan complejidades diferentes debido a su implementaci n).