PDF de programación - Introducción al análisis de algoritmos - Introducción a la programación con Python y C

Tema 14

Introducción al análisis 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én ha ganado?)).
El Dodo no podía contestar a esta pregunta sin meditarlo mucho antes, y permaneció largo
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ón de
qué escogerías?: ¿de su elegancia?, ¿de la legibilidad?, ¿del interfaz de usuario?, ¿de su velocidad de
ejecución?, ¿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án los métodos de resolución de problemas,
es decir, los algoritmos, y no los programas, o sea, sus implementaciones concretas usando diferentes
lenguajes de programación.

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
óptimo con mínimo coste temporal; es más, ambos factores entrarán, normalmente, en competencia.
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 algorit-
mos. Empezaremos proponiendo una aproximación empírica consistente en implementar diferentes
programas que resuelven un mismo problema (con el mismo o diferentes algoritmos) y medir y com-
parar los tiempos de ejecución. Veremos que, en principio, resulta más determinante una correcta
elección del algoritmo que los detalles de implementación o, incluso, que la elección de un lenguaje
de programación frente a otro. La aproximación empírica supone un notable esfuerzo en tanto que
obliga a implementar diferentes programas, prepararlos para hacer factible la medida de tiempos y
realizar diferentes experimentos que nos permitan extraer conclusiones. Presentaremos una aproxi-
mación más teórica que permitirá arrojar luz sobre la eficiencia de los algoritmos sin necesidad de
implementarlos y realizar experimentos.

14.1. Complejidad temporal: una aproximación empírica

La aproximación empírica se basa en la realización de estudios comparativos basados en la realización
de experimentos de medición de tiempos de ejecución. Ilustraremos el problema de la medición de

Volumen II: C

345

14.1 Complejidad temporal: una aproximación empírica

versión 1.02

tiempos con un ejemplo concreto. Mediremos tiempo de ejecución con varios programas que resuelven
un mismo problema: la ordenación de un vector de enteros. Naturalmente, el tiempo de ejecución
dependerá del tamaño del vector a ordenar, así que nuestro estudio considerará la dependencia del
tiempo en función de dicho tamaño.

Empecemos presentando un programa Python que resuelve el problema mediante el método de

la burbuja:

fromfrom random import

import randrange

ordena_burbuja.py

defdef rellena

rellena (talla, rango):

valores = [0] * talla
forfor i inin range(talla):

valores[i] = randrange(0, rango)

return
return valores

defdef burbuja

burbuja (valores):

nuevo = valores[:]
forfor i inin range(len(nuevo)):

forfor j inin range(len(nuevo)-1-i):

ifif nuevo[j] > nuevo[j+1]:

nuevo[j], nuevo[j+1] = nuevo[j+1], nuevo[j]

return
return nuevo

# Programa principal
talla = 1000
rango = 100000

vector = rellena(talla, rango)

print
print "Vector desordenado: ", vector
ordenado = burbuja(vector)
print
print "Vector ordenado: ", ordenado

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

El programa define dos funciones: rellena y burbuja. La primera crea un vector con talla elementos
enteros de valor aleatorio (la llamada randrange(0, rango) selecciona un entero al azar entre 0 y
rango menos uno). La segunda función ordena y devuelve una copia del vector que se le suministra
como parámetro.

El programa principal solicita la creación de un vector con 1000 enteros (con valores aleatorios
entre 0 y 99999), muestra por pantalla el resultado, ordena el vector y vuelve a mostrar el resultado
en pantalla. Aquí tienes un ejemplo (resumido) de la salida por pantalla que produce una ejecución
del programa:

$ python ordena_burbuja.py
python ordena_burbuja.py
Vector desordenado: [41689, 56468, 40098, 49718, 72475, ..., 97318, 10805, 55123]
Vector ordenado: [9, 14, 37, 38, 44, 48, 71, 95, 56782, ..., 99957, 99976, 99983]

¿Cómo podemos medir el tiempo de ejecución de la función burbuja? Una posibilidad es usar un
cronómetro de mano, pulsar el botón de inicio justo en el instante en que pulsamos la tecla de retorno
de carro y pulsar el botón de parada cuando se imprime el resultado de ordenar el vector. Mmmm.
Pero así estaríamos midiendo el tiempo total de ejecución del programa. ¿Cómo medir únicamente
el tiempo de burbuja? ¡Pulsando los botones de arranque y parada del cronómetro justo después
de que salga el mensaje que empieza con ((Vector desordenado)) y en el preciso instante en que
aparece el texto ((Vector ordenado)). ¿Podemos hacerlo? Ten en cuenta que el tiempo de ejecución
puede rondar las ¡milésimas o centésimas de segundo! Tranquilo, no hace falta tener unos reflejos
prodigiosos para medir el tiempo de ejecución de una función.

346

Introducción a la programación con Python y C

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

c 2002 de Andrés Marzal e Isabel Gracia

14 Introducción al análisis de algoritmos

14.1.1. Medida de tiempo de ejecución en Python: la función clock

El módulo time ofrece una función para la medición de tiempos. Su nombre es clock y devuelve
el número de segundos que ha dedicado la CPU a la ejecución programa hasta el punto en que se
efectúa la llamada a la función. El valor devuelto es un flotante. Aquí tienes una versión del programa
ordena burbuja.py que mide únicamente el tiempo de ejecución de la ordenación por burbuja.

fromfrom random import
fromfrom time import

import clock

import randrange

ordena_burbuja.py

defdef rellena

rellena (talla, rango):

valores = [0] * talla
forfor i inin range(talla):

valores[i] = randrange(0, rango)

return
return valores

defdef burbuja

burbuja (valores):

nuevo = valores[:]
forfor i inin range(len(nuevo)):

forfor j inin range(len(nuevo)-1-i):

ifif nuevo[j] > nuevo[j+1]:

nuevo[j], nuevo[j+1] = nuevo[j+1], nuevo[j]

# Programa principal
talla = 1000
rango = 100000

vector = rellena(talla, rango)

print
print "Vector desordenado: ", vector
tiempo_inicial = clock()
ordenado = burbuja(vector)
tiempo_final = clock()
print
print "Vector ordenado: ", ordenado

print
print "Tiempo de ejecución de burbuja: %f " % (tiempo_final - tiempo_inicial)

Aquí tienes el resultado de ejecutar el programa:

$ python ordena_burbuja.py
python ordena_burbuja.py
Antes de ordenar: [41689, 56468, 40098, 49718, 72475, ..., 97318, 10805, 55123]
Después de ordenar: [9, 14, 37, 38, 44, 48, 71, 95, ..., 99957, 99976, 99983]
Tiempo de ejecución de burbuja: 0.660000

La ejecución del método de la burbuja ha requerido 66 centésimas1. La resolución del reloj que
consulta clock es de una centésima, así que no cabe esperar obtener más de dos decimales en
nuestras medidas.

Debes tener en cuenta que la medida de clock se puede ver afectada por cierto grado de error.

Si volvemos a ejecutar el programa, obtenemos una medida ligeramente diferente:

$ python ordena_burbuja.py
python ordena_burbuja.py
Antes de ordenar: [41689, 56468, 40098, 49718, 72475, ..., 97318, 10805, 55123]

1 Esta medida se ha realizado ejecutando el programa en un ordenador Pentium IV Xeon a 2.0 GHz, dual, con 2
gigabytes de memoria RAM, corriendo bajo el sistema operativo Linux con núcleo 2.4.19, con la versión 2.2.1 del
intérprete Python compilado con la versión 3.2 de gcc. . . Es posible que obtengas resultados muy diferentes si haces el
experimento en tu ordenador y/o con un sistema operativo diferente y/o otra versión del intérprete Python. . . O sea,
que el valor de tiempo obtenido significa, por sí mismo, más bien poco. Tendrá interés, en todo caso, cuando deseemos
comparar la eficiencia de dos programas diferentes para efectuar un estudio comparativo.

Volumen II: C

347

14.1 Complejidad temporal: una aproximación empírica

versión 1.02

Después de ordenar: [9, 14, 37, 38, 44, 48, 71, 95, ..., 99957, 99976, 99983]
Tiempo de ejecución de burbuja: 0.690000

Aquí tienes las medidas obtenidas tras 10 ejecuciones:

0.66

0.69

0.69

0.70

0.67

0.70

0.70

0.68

0.69

0.68

Tendremos que recurrir a la estadística descriptiva para proporcionar información acerca del tiempo
de ejecución. La media del tiempo de ejecución es de 0.686 segundos (y su desviación estándar,
0.0135).

14.1.2. Tiempo medio de ejecución

Mmmm. Como estamos programando, podemos automatizar el proceso de medición y obtención
de estadísticas (eliminamos en ésta y posteriores versiones la impresión por pantalla de los vector
desordenado y ordenado, pues no influye en la medición de tiempos y llena la pantalla de información
que no nos resulta útil):

fromfrom random import
fromfrom time import

import clock

import randrange

ordena_burbuja.py

defdef rellena

rellena (talla, rango):

valores = [0] * talla
forfor i inin range(talla):

valores[i] = randrange(0, rango)

return
re