Algoritmos

Tema 14

Introducci´n al an´lisis de algoritmos
o
a
Sin embargo, cuando ya llevaban corriendo una media hora o as´ y estaban completamente
ı,
secos otra vez, el Dodo dijo de repente en voz alta: ((¡La carrera ha terminado!)), y se agruparon
todos a su alrededor, jadeando y preguntado: ((Pero, ¿qui´n ha ganado?)).
e
El Dodo no pod´ contestar a esta pregunta sin meditarlo mucho antes, ypermaneci´ largo
ıa
o
rato con un dedo apretado en la frente (en la postura que normalmente veis a Shakespeare
en los retratos), mientras el resto esperaba en silencio.
LEWIS CARROLL, Alicia en el Pa´ de las Maravillas.
ıs
Si tuvieses que escoger un programa entre varios que resuelven un mismo problema, ¿en funci´n de
o
qu´ escoger´
e
ıas?: ¿de su elegancia?, ¿de la legibilidad?, ¿delinterfaz de usuario?, ¿de su velocidad de
ejecuci´n?, ¿de la memoria que consume? No cabe duda de que todos los factores influyen. Nosotros
o
consideraremos aqu´ criterios basados en la eficiencia, es decir, en el mejor aprovechamiento de los
ı
recursos computacionales. Nuestro objeto de estudio ser´n los m´todos de resoluci´n de problemas,
a
e
o
es decir, los algoritmos, y no los programas,o sea, sus implementaciones concretas usando diferentes
lenguajes de programaci´n.
o
Estudiaremos dos factores:
El coste o complejidad espacial, es decir, la cantidad de memoria que consume.
El coste o complejidad temporal, o sea, el tiempo que necesita para resolver un problema.
Ambos determinan el coste o complejidad computacional. No siempre coincidir´n consumo espacial
a
o
´ptimo conm´
ınimo coste temporal; es m´s, ambos factores entrar´n, normalmente, en competencia.
a
a
En ocasiones estaremos obligados, pues, a adoptar compromisos razonables entre ambos costes.
Centraremos el estudio, principalmente, en el an´lisis de la complejidad temporal de los algorita
mos. Empezaremos proponiendo una aproximaci´n emp´
o
ırica consistente en implementar diferentes
programasque resuelven un mismo problema (con el mismo o diferentes algoritmos) y medir y comparar los tiempos de ejecuci´n. Veremos que, en principio, resulta m´s determinante una correcta
o
a
elecci´n del algoritmo que los detalles de implementaci´n o, incluso, que la elecci´n de un lenguaje
o
o
o
de programaci´n frente a otro. La aproximaci´n emp´
o
o
ırica supone un notable esfuerzo en tantoque
obliga a implementar diferentes programas, prepararlos para hacer factible la medida de tiempos y
realizar diferentes experimentos que nos permitan extraer conclusiones. Presentaremos una aproximaci´n m´s te´rica que permitir´ arrojar luz sobre la eficiencia de los algoritmos sin necesidad de
o
a
o
a
implementarlos y realizar experimentos.

14.1.

Complejidad temporal: una aproximaci´nemp´
o
ırica

La aproximaci´n emp´
o
ırica se basa en la realizaci´n de estudios comparativos basados en la realizaci´n
o
o
de experimentos de medici´n de tiempos de ejecuci´n. Ilustraremos el problema de la medici´n de
o
o
o
Volumen II: C

345

14.1 Complejidad temporal: una aproximaci´n emp´
o
ırica

versi´n 1.02
o

tiempos con un ejemplo concreto. Mediremos tiempo deejecuci´n con varios programas que resuelven
o
un mismo problema: la ordenaci´n de un vector de enteros. Naturalmente, el tiempo de ejecuci´n
o
o
depender´ del tama˜o del vector a ordenar, as´ que nuestro estudio considerar´ la dependencia del
a
n
ı
a
tiempo en funci´n de dicho tama˜o.
o
n
Empecemos presentando un programa Python que resuelve el problema mediante el m´todo de
e
laburbuja:
ordena_burbuja.py
1

from random import randrange

2
3
4
5
6
7

def rellena (talla, rango):
valores = [0] * talla
for i in range(talla):
valores[i] = randrange(0, rango)
return valores

8
9
10
11
12
13
14
15

def burbuja (valores):
nuevo = valores[:]
for i in range(len(nuevo)):
for j in range(len(nuevo)-1-i):
if nuevo[j] > nuevo[j+1]:
nuevo[j], nuevo[j+1]...