Introducci N Al An Lisis De Algoritmos

Tema 14

Introducci´
on al an´
alisis de algoritmos
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´en ha ganado?✮✮.
El Dodo no pod´ıa contestar a esta pregunta sin meditarlo mucho antes, y permaneci´olargo
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´ıs de las Maravillas.
Si tuvieses que escoger un programa entre varios que resuelven un mismo problema, ¿en funci´
on de
qu´e escoger´ıas?: ¿de su elegancia?, ¿de la legibilidad?, ¿del interfaz de usuario?, ¿de suvelocidad de
ejecuci´on?, ¿de la memoria que consume? No cabe duda de que todos los factores influyen. Nosotros
consideraremos aqu´ı criterios basados en la eficiencia, es decir, en el mejor aprovechamiento de los
recursos computacionales. Nuestro objeto de estudio ser´an los m´etodos de resoluci´on de problemas,
es decir, los algoritmos, y no los programas, o sea, sus implementaciones concretasusando diferentes
lenguajes de programaci´on.
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´an consumo espacial
´optimo con m´ınimo coste temporal; es m´as, ambos factoresentrar´an, normalmente, en competencia.
En ocasiones estaremos obligados, pues, a adoptar compromisos razonables entre ambos costes.
Centraremos el estudio, principalmente, en el an´alisis de la complejidad temporal de los algoritmos. Empezaremos proponiendo una aproximaci´on emp´ırica consistente en implementar diferentes
programas que resuelven un mismo problema (con el mismo o diferentesalgoritmos) y medir y comparar los tiempos de ejecuci´on. Veremos que, en principio, resulta m´as determinante una correcta
elecci´on del algoritmo que los detalles de implementaci´on o, incluso, que la elecci´on de un lenguaje
de programaci´on frente a otro. La aproximaci´on emp´ırica supone un notable esfuerzo en tanto que
obliga a implementar diferentes programas, prepararlos para hacer factible lamedida de tiempos y
realizar diferentes experimentos que nos permitan extraer conclusiones. Presentaremos una aproximaci´on m´as te´
orica que permitir´a arrojar luz sobre la eficiencia de los algoritmos sin necesidad de
implementarlos y realizar experimentos.

14.1.

Complejidad temporal: una aproximaci´
on emp´ırica

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

345

14.1 Complejidad temporal: una aproximaci´on emp´ırica

versi´
on 1.02

tiempos con un ejemplo concreto. Mediremos tiempo de ejecuci´on con varios programas que resuelven
un mismo problema: la ordenaci´on de un vector de enteros. Naturalmente, el tiempo deejecuci´on
depender´a del tama˜
no del vector a ordenar, as´ı que nuestro estudio considerar´a la dependencia del
tiempo en funci´on de dicho tama˜
no.
Empecemos presentando un programa Python que resuelve el problema mediante el m´etodo de
la burbuja:
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] = nuevo[j+1], nuevo[j]
return nuevo

16
17
18
19

# Programa principal
talla = 1000
rango = 100000

20
21

vector = rellena(talla, rango)

22
23
24
25

print "Vector desordenado: ",...