PDF de programación - Capítulo 1 - LA COMPLEJIDAD DE LOS ALGORITMOS

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 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.
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 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. 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. 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.


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.
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).

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 200.000.
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). 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.
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.), 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). Sin embargo, en este texto tendremos en
cuenta, a menos que se indique lo contrario, todas las operaciones elementales del
lenguaje, y supondremos que sus tiempos de ejecución son todos iguales.
Para hacer un estudio del tiempo de ejecución de un algoritmo para los tres
casos citados comenzaremos con un ejemplo concreto. Supongamos entonces que
disponemos de la definición de los siguientes tipos y constantes:

4



TÉCNICAS DE DISEÑO DE ALGORITMOS

CONST n =...; (* num. maximo de elementos de un vector *);
TYPE vector = ARRAY [1..n] OF INTEGER;


y de un algoritmo cuya implementación en Modula-2 es:


PROCEDURE Buscar(VAR a:vector;c:INTEGER):CARDINAL;
VAR j:CARDINAL;
BEGIN
j:=1; (* 1 *)
WHILE (a[j]<c) AND (j<n) DO (* 2 *)
j:=j+1 (* 3 *)
END; (* 4 *)
IF a[j]=c THEN (* 5 *)
RETURN j (* 6 *)
ELSE RETURN 0 (* 7 *)
END (* 8 *)
END Buscar;


Para determinar el tiempo de ejecución, calcularemos primero el n