PDF de programación - Tema 2. Análisis de la eficiencia - Estructuras de Datos y Algoritmos

Estructuras de Datos 

y Algoritmos

Tema 2. Análisis de la eficiencia

Prof. Dr. P. Javier Herrera

Contenido

•
•

Introducción a la eficiencia computacional
Cálculo básico de complejidades

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

22

Una leyenda ajedrecística

• Mucho tiempo atrás, el espabilado visir Sissa ben Dahir inventó el juego del ajedrez 
para el rey Shirham de la India. El rey ofreció a Sissa la posibilidad de elegir su propia 
recompensa. Sissa le dijo al rey que podía recompensarle en trigo con una cantidad 
equivalente a la cosecha de trigo en su reino de dos años, o bien con una cantidad de 
trigo que se calcularía de la siguiente forma:
– un grano de trigo en la primera casilla de un tablero de ajedrez,
– mas dos granos de trigo en la segunda casilla,
– mas cuatro granos de trigo en la tercera casilla,
– y así sucesivamente, duplicando el número de granos en cada casilla, hasta llegar a la última 

casilla.

•

•

El rey pensó que la primera posibilidad era demasiado cara mientras que la segunda, 
medida además en simples granos de trigo, daba la impresión de serle claramente 
favorable.

Así que sin pensárselo dos veces pidió que trajeran un saco de trigo para hacer la 
cuenta sobre el tablero de ajedrez y recompensar inmediatamente al visir.

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

33

¿Es una buena elección?

•

•

El número de granos en la primera fila resultó ser:

0

2



2
1



2

2



3

2



4

2



5

2



6

2



7

2



255

La cantidad de granos en las dos primeras filas es:

15



i



0

i

2



2
16

1


535 65

• Al llegar a la tercera fila el rey empezó a pensar que su elección no había sido 

acertada, pues para llenar las tres filas necesitaba

23



i



0

i

2

24



2

1


216 777 16

granos, que pesan alrededor de 600 kilos …

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

4
4

Endeudado hasta las cejas

•

•

•

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

i



2

63

i

0

64

2

1


615 551 709 073 744 446 18



10*84,1
19

granos, cantidad equivalente a las cosechas mundiales actuales de 1000 años.

La función 2n − 1 (exponencial) representa el número de granos adeudados en 
función del número n de casillas a rellenar. Toma valores desmesurados aunque el 
número de casillas sea pequeño.

El coste en tiempo de algunos algoritmos expresado en función del tamaño de los 
datos de entrada es también exponencial. Por ello es importante estudiar el coste 
de los algoritmos y ser capaces de comparar los costes de algoritmos que 
resuelven un mismo problema.

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

5
5

Motivación

•

•

•

Entendemos por eficiencia el rendimiento de una actividad en relación con el 
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 
10 
102
103
104
105
106

log10n
1 ms 
2 ms 
3 ms 
4 ms 
5 ms 
6 ms 

n 

10 ms 
0,1 s 
1 s 
10 s 
1,67 m 
16,67 m 

n log10n
10 ms 
0,2 s 
3 s 
40 s 
8,33 m 
1,67 h 

n2
0,1 s 
10 s 

16,67 m 
1,16 d 
115,74 d 
31,71 a 

2n

1,02 s 

n3
1 s 

4,02 ∗ 1020 sig
3,4 ∗ 10291 sig
6,3 ∗ 103000 sig
3,16 ∗ 1030093 sig
317 097,9 sig 3,1 ∗ 10301020 sig

16,67 m 
11,57 d 
31,71 a 
317,1 sig 

Es un error pensar que basta esperar algunos años para que algoritmos tan 
costosos se puedan ejecutar con un coste en tiempo razonable.

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

6
6

¿Qué medimos y cómo?

•

La eficiencia es mayor cuanto menor es la complejidad o el coste (consumo de 
recursos).

• Necesitamos determinar cómo se ha de medir el coste de un algoritmo, de forma 
que sea posible compararlo con otros que resuelven el mismo problema y decidir 
cuál de todos es el más eficiente.

• Una posibilidad para medir el coste de un algoritmo es contar cuántas 

instrucciones de cada tipo se ejecutan, multiplicar este número por el tiempo que 
emplea la instrucción en ejecutarse, y realizar la suma para los diferentes tipos.

ta =    tiempo de asignación
tc =    tiempo de comparación
ti =    tiempo de incremento
tv =    tiempo de acceso a un vector

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

77

Ejemplo

•

Ordenación por selección del vector V[1..n]

para i := 1 hasta n − 1 hacer

pmin := i ;
para j = i + 1 hasta n hacer

si V[j] < V[pmin] entonces pmin := j fsi

fpara ;
intercambiar(V[i],V[pmin])

fpara

– Control del primer bucle: ta + (n − 1)ti + ntc
– Primera asignación: (n − 1)ta
– Control del bucle interno, para cada i: ta + (n − i)ti + (n − i + 1)tc
– instrucción si, para cada i, tiempo mínimo: (n − i)(2tv + tc)

tiempo máximo: (n − i)(2tv + tc) + (n − i)ta

– Intercambiar: (n −1)(2tv + 3ta)

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

88

Ejemplo

•

El bucle interno en total en el caso peor, el más desfavorable,

n

1



i

1



t

a



t

c


in



t

i



t
2

c



t
2

v



t

a




• Concluimos que

Tmín = An2 − Bn + C
Tmáx = A′n2 − B′n + C′

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

9
9

Factores

•

El tiempo de ejecución de un algoritmo depende en general de tres 
factores:

1. El tamaño de los datos de entrada. Por ejemplo:

• Para un vector: su longitud.
• Para un número natural: su valor o el número de dígitos.
• Para un grafo: el número de vértices y/o el número de aristas.

2. El contenido de esos datos.

3. El código generado por el compilador y el ordenador concreto 

utilizados.

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

1010

Factores

•

Si el tiempo que tarda un algoritmo A en procesar una entrada concreta 
denotamos por 

x
, definimos la complejidad de A en el caso peor como

 x

t A

lo 

 
nT
A




máx

 
xt
A

|

x
de

tamaño

n


• Otra posibilidad es realizar un análisis de la eficiencia en el caso promedio. Para 
ello necesitamos conocer el tiempo de ejecución de cada posible ejemplar y la 
frecuencia con que se presenta, es decir, su distribución de probabilidades. 
Definimos la complejidad de un algoritmo A en el caso promedio como

TM

 
n

A



x
de

tamaño

 
txp

n


 
x

A

siendo 

 
1..0xp



la probabilidad de que la entrada sea     
x

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

11
11

Medidas asintóticas

•

•

•

•

El único factor del que van a depender las funciones que representan el coste de un 
algoritmo es el tamaño de los datos de entrada. Por eso, trabajamos con funciones

. No nos importa tanto las funciones concretas, sino la forma en la que 

crecen.
Definición: El conjunto de las funciones del orden de f (n), denotado O(f (n)), se define como

Asimismo, diremos que una función g es del orden de f (n) cuando g∈ O(f (n)).

Decimos que el conjunto O(f (n)) define un orden de complejidad.

Si el tiempo de un algoritmo está descrito por una función T(n) ∈ O(f (n)) diremos que el 

tiempo de ejecución del algoritmo es del orden de f (n).

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

1212

Propiedades

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

1313

Teorema del límite

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

1414

Ejemplos

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

1515

Jerarquía de órdenes de complejidad

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

1616

Órdenes de complejidad

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

1717

Órdenes de complejidad

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

1818

Órdenes de complejidad

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

1919

Cotas inferiores

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2020

Teorema del límite

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2121

Orden exacto

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2222

Teorema del límite

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2323

Análisis de algoritmos

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2424

Ejemplos

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2525

Ejemplos

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2626

Ejemplos

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2727

Instrucción crítica

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2828

Ejemplo

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

2929

Limitaciones prácticas

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

3030

Formulas útiles para el análisis de algoritmos

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

3131

Formulas útiles para el análisis de algoritmos

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

3232

Ejercicio propuesto

• Calcular el coste (en el caso caso peor) de los algoritmos que aparecen en 
las páginas 8, 25, 26, 27. Realizarlo de la forma explicada en la página 7, y 
de la forma simplificada explicada en la página 24.

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

3333

Bibliografía

•

Peña, R.; Diseño de programas. Formalismo y abstracción. Tercera edición. Prentice Hall, 
2005. Capítulo 1

• Martí, N., Palomino, M., Verdejo, J. A. Introducción a la computación. Colección Base 

Universitaria, Anaya, 2006. Capítulo 4

• Martí, N., Segura, C. M., Verdejo, J. A. Especificación, derivación y análisis de algoritmos. 

Colección Prentice Practica, Pearson, Prentice Hall, 2006. Capítulo 3

(Estas transparencias se han realizado a partir de aquéllas desarrolladas por los profesores 
Alberto Verdejo y Rafael del Vado de la UCM, y basadas en la bibliografía anterior)

Tema 2. Análisis de la eficiencia ‐ Curso 2014/15

3434