Complejidad

An´lisis de la complejidad de algoritmos
a
Rafael del Vado V´
ırseda
Dpto. de Sistemas Inform´ticos y Computaci´n
a
o
Universidad Complutense de Madrid
Curso 2008-2009

Rafael del Vado V´
ırseda (UCM)

1 / 37

Bibliograf´
ıa

• Pe˜a, R. Dise˜o de programas. Formalismo y abstracci´n (Tercera Edici´n). Prentice
n
n
o
o
Hall, 2005.
Cap´
ıtulo 1
• Mart´ Oliet, N.; PalominoTarjuelo, M.; Verdejo L´pez, J. A. Introducci´n a la
ı
o
o
computaci´n. Colecci´n Base Universitaria, Anaya, 2006.
o
o
Cap´
ıtulo 4
• Mart´ Oliet, N.; Segura D´ C. M.; Verdejo L´pez, J. A. Especificaci´n, derivaci´n
ı
ıaz,
o
o
o
y an´lisis de algoritmos. Colecci´n Prentice Practica, Pearson, Prentice Hall, 2006.
a
o
Cap´
ıtulo 3

Rafael del Vado V´
ırseda (UCM)

2 / 37Una leyenda ajedrec´
ıstica
Mucho tiempo atr´s, el espabilado visir Sissa ben Dahir invent´ el juego del ajedrez para
a
o
el rey Shirham de la India. El rey ofreci´ a Sissa la posibilidad de elegir su propia
o
recompensa. Sissa le dijo al rey que pod´ recompensarle en trigo o bien con una
ıa
cantidad equivalente a la cosecha de trigo en su reino de dos a˜os, o bien con una
n
cantidad detrigo que se calcular´ de la siguiente forma:
ıa
• un grano de trigo en la primera casilla de un tablero de ajedrez,
• m´s dos granos de trigo en la segunda casilla,
a
• m´s cuatro granos de trigo en la tercera casilla,
a
• y as´ sucesivamente, duplicando el n´mero de granos en cada casilla, hasta llegar a
ı
u

la ultima casilla.
´
El rey pens´ que la primera posibilidad era demasiadocara mientras que la segunda,
o
medida adem´s en simples granos de trigo, daba la impresi´n de serle claramente
a
o
favorable.
As´ que sin pens´rselo dos veces pidi´ que trajeran un saco de trigo para hacer la cuenta
ı
a
o
sobre el tablero de ajedrez y recompensar inmediatamente al visir.

Rafael del Vado V´
ırseda (UCM)

3 / 37

¿Es una buena elecci´n?
o

El n´mero de granosen la primera fila result´ ser:
u
o
20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 = 255
La cantidad de granos en las dos primeras filas es:
15

∑ 2i = 216 − 1 = 65 535
i=0

Al llegar a la tercera fila el rey empez´ a pensar que su elecci´n no hab´ sido acertada,
o
o
ıa
pues para llenar las tres filas necesitaba
23

∑ 2i = 224 − 1 = 16 777 216
i=0

granos, que pesan alrededor de 600 kilos. . .

Rafael del Vado V´
ırseda (UCM)

4 / 37

Endeudado hasta las cejas

En efecto, para rellenar las 64 casillas del tablero hacen falta
63

∑ 2i = 264 − 1 = 18 446 744 073 709 551 615 ≈ 1,84 ∗ 1019
i=0

granos, cantidad equivalente a las cosechas mundiales actuales de 1000 a˜os!!.
n
La funci´n 2n − 1 (exponencial) representa el n´mero de granos adeudados en funci´n del
o
uo
n´mero n de casillas a rellenar. Toma valores desmesurados aunque el n´mero de casillas
u
u
sea peque˜o.
n
El coste en tiempo de algunos algoritmos expresado en funci´n del tama˜o de los datos de
o
n
entrada es tambi´n exponencial. Por ello es importante estudiar el coste de los algoritmos
e
y ser capaces de comparar los costes de algoritmos que resuelven un mismo problema.

Rafaeldel Vado V´
ırseda (UCM)

5 / 37

Motivaci´n
o

• Entendemos por eficiencia el rendimiento de una actividad en relaci´n con el
o
consumo de un cierto recurso. Es diferente de la efectividad.
• Ejemplo para ver la importancia de que el coste del algoritmo sea peque˜o.
n
n
10

log10 n
1 ms

n
10 ms

102

2 ms

0,1 s

103

3 ms

104
5

n log10 n

2n
1,02 s

10ms

n2
0,1 s

n3
1s

0,2 s

10 s

16,67 m

4,02 ∗ 1020 sig

1s

3s

16,67 m

11,57 d

3,4 ∗ 10291 sig

4 ms

10 s

40 s

1,16 d

31,71 a

6,3 ∗ 103000 sig

10

5 ms

1,67 m

8,33 m

115,74 d

317,1 sig

3,16 ∗ 1030093 sig

106

6 ms

16,67 m

1,67 h

31,71 a

317 097,9 sig

3,1 ∗ 10301020 sig

• Es un error pensar que basta...