Analisis

An´lisis de Algoritmos
a
Amalia Duch
Barcelona, marzo de 2007

´
Indice
1. Costes en tiempo y en espacio

1

2. Coste en los casos mejor, promedio y peor

3

3. Notaci´n asint´tica
o
o

4

4. Coste de los algoritmos iterativos

6

5. Coste de los algoritmos recursivos, teoremas maestros

6

1.

Costes en tiempo y en espacio

La caracter´
ıstica b´sica que debetener un algoritmo es que sea correcto,
a
es decir, que produzca el resultado deseado en tiempo finito. Adicionalmente
puede interesarnos que sea claro, que est´ bien estructurado, que sea f´cil de
e
a
usar, que sea f´cil de implementar y que sea eficiente.
a
Entendemos por eficiencia de un algoritmo la cantidad de recursos de
c´mputo que requiere; es decir, cu´l es su tiempo de ejecuci´n yqu´ cantidad
o
a
o
e
de memoria utiliza.
A la cantidad de tiempo que requiere la ejecuci´n de un cierto algoritmo se
o
le suele llamar coste en tiempo mientras que a la cantidad de memoria que
requiere se le suele llamar coste en espacio.
Es evidente que conviene buscar algoritmos correctos que mantengan tan bajo como sea posible el consumo de recursos que hacen del sistema, es decir, quesean lo m´s eficientes posible. Cabe hacer notar que el concepto de eficiencia
a
de un algoritmo es un concepto relativo, esto quiere decir que ante dos algoritmos correctos que resuelven el mismo problema, uno es m´s eficiente que
a
otro si consume menos recursos. Por tanto, podemos observar que el concepto
de eficiencia y en consecuencia el concepto de coste nos permitir´ comparar
a
distintosalgoritmos entre ellos.
Si consideramos los algoritmos elementales de ordenaci´n por selecci´n y por
o
o
inserci´n ¿c´mo podr´
o
o
ıamos elegir cu´l de ellos utilizar en una aplicaci´n dada?
a
o

1

Veremos m´s adelante que para efectos pr´cticos ambos algoritmos son similares
a
a
y que son eficientes s´lo para ordenar secuencias con un n´mero peque˜o de
o
u
n
elementos. Sinembargo hay varias comparaciones que se pueden hacer entre
ellos.

Selecci´n
o

Tama˜o del vector
n
n

Inserci´n
o

n

Num. Comparaciones
n(n − 1)/2
n − 1 (min.)
prop. n2 /4 (prom.)
prop. n2 /2 (max.)

Num. Intercambios
0 (min.)
n − 1 (max.)
0 (min.)
prop. n2 /4 (prom.)
prop. n2 /2

De la tabla anterior podemos inferir que para ordenar secuencias cuyos elementos seandif´
ıciles de comparar (las comparaciones son caras) es m´s convea
niente utilizar el m´todo de ordenaci´n por inserci´n, y que este m´todo es m´s
e
o
o
e
a
eficiente mientras m´s ordenada est´ la secuencia de entrada. Si por el contrario
a
e
queremos ordenar secuencias de elementos que son f´ciles de comparar (o que
a
tienen claves asociadas f´ciles de comparar) y en cambio losintercambios son
a
caros ser´ m´s conveniente utilizar el algoritmo de ordenaci´n por selecci´n.
ıa a
o
o
En general, ¿c´mo podemos elegir entre un algoritmo y otro si ambos resuelo
ven el mismo problema?
Una posibilidad es hacerlo mediante pruebas emp´
ıricas. En este caso
habr´ que traducir ambos algoritmos a un lenguaje de programaci´n, realiıa
o
zar medidas del tiempo de ejecuci´n de losprogramas cuando se aplican a un
o
conjunto de muestras de entrada y a partir de estas medidas intentar inferir el
rendimiento de los programas. Pero este m´todo tiene varios inconvenientes
e
ya que los resultados dependen:
del subconjunto de pruebas escogidas
del ordenador en el que se realicen las pruebas
del lenguaje de programaci´n utilizado o
o
del compilador, entre otros factores.Adem´s, no siempre es f´cil implementar un algoritmo (algunos pueden ser
a
a
muy largos o complicados), por tanto, en muchas ocasiones puede ser muy util
´
poder predecir c´mo va a comportarse un algoritmo sin tenerlo que implemeno
tar. Para ello es conveniente analizar un algoritmo matem´ticamente.
a
Ejemplo. An´lisis de la funci´n pos min, que encuentra la posici´n del elea
o
o...