PDF de programación - Tema 1. Eficiencia de los algoritmos - Técnicas de Programación Avanzadas (TPA)

Técnicas de Programación Avanzadas

(TPA)

Tema 1. Eficiencia de los

algoritmos

Tema 1. Eficiencia de los algoritmos

1. Criterios para medir la eficiencia de un algoritmo
2. Tiempo de ejecución
3. Orden de magnitud
4. Reglas para calcular la complejidad del código
5. Complejidad en código recursivo

20/1/17

1

Técnicas de Programación Avanzadas (TPA)

Criterios para medir la eficiencia de un algoritmo

§ Para un mismo problema se pueden diseñar distintos

algoritmos (soluciones) que lo resuelvan correctamente.

§ Debe poderse determinar qué algoritmo utilizar.

§ Ejemplo: ¿Cuál es la mejor ruta?

– La más corta.
– La más rápida.
– La que no tenga peajes.

Técnicas de Programación Avanzadas (TPA)

Criterios para medir la eficiencia de un algoritmo

§ Para ello se compararán según un criterio determinado. Los

más usuales:
– Legibilidad y facilidad de comprensión, codificación y depuración.
– Uso eficiente de los recursos: tiempo de ejecución y espacio de

memoria.

– (Otros: reutilización, documentación, portabilidad, etc.)

§ Mediremos la eficiencia según el segundo de los criterios (los

primeros se presuponen).

20/1/17

2

Técnicas de Programación Avanzadas (TPA)

Criterios para medir la eficiencia de un algoritmo

§ La memoria ya no es un recurso crítico à mediremos la
eficiencia de un algoritmo basándonos casi siempre en su
tiempo de ejecución.

§ El tiempo de ejecución no dependerá de la potencia de la

máquina donde se ejecuta. Habrá que estudiarlo en función
del algoritmo utilizado.

Tema 1. Eficiencia de los algoritmos

1. Criterios para medir la eficiencia de un algoritmo
2. Tiempo de ejecución
3. Orden de magnitud
4. Reglas para calcular la complejidad del código
5. Complejidad en código recursivo

20/1/17

3

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

§

En general, el tiempo de ejecución de un programa depende
de varios factores:

1. Nº de veces que se ejecuta cada instrucción.
2. Compilador utilizado (una instrucción de alto nivel se

puede traducir a lenguaje máquina de diferentes
formas).

3. El ordenador utilizado (puede variar el tiempo de

ejecución de cada instrucción máquina).

§ Nos basaremos sólo en el primer factor. Los demás no se

pueden presuponer.

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

§

§

Realizaremos una estimación a priori de la frecuencia de
ejecución.

En el tiempo de ejecución de un caso concreto también
influye:

– Nº de datos de entrada,
– Estructura de la entrada,
– Distribución de la entrada.
– Calidad del código fuente y calidad del código

máquina è no se calcula el nº de instrucciones
ejecutadas, sino el nº de veces que se ejecuta cada
instrucción.

20/1/17

4

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

§

§

Dependiendo de la entrada del problema, pueden darse 3
casos:

• Caso Peor: el tiempo de ejecución es máximo.
• Caso Mejor: el tiempo de ejecución es mínimo.
• Caso Medio: caso más probable. Tiempo de ejecución

= media estadística de todos los casos posibles.

Para probar la eficiencia de un algoritmo usaremos como
medida el tiempo de ejecución en el peor caso: T(n).

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

§

2

4

6

Ejemplo:
–

¿Cuántas veces se ejecuta cada instrucción si el tamaño N
de la lista es 4? ¿Y si es 6?

boolean buscar (TElemento item, Lista L) {

{Pre: N>0}
{Post: Buscar = $i:1<=i<=N: L[i]=item}
boolean encontrado = false;
int cont = 0;
while ((!encontrado) && (cont < L.longitud())){

cont++;
encontrado = L[cont] == item;

}
return encontrado;

1

3

5

}

20/1/17

5

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

§

En el peor de los casos:

Instrucción

1
2
3

4
5
6

Código

boolean encontrado = false;
int cont = 0;
while ((!encontrado) &&
(cont < L.longitud()))
cont++;
encontrado = L[cont] == item;
return encontrado;

Ejecuciones

1
1
n+1

n
n
1

Total

3n+4

– A medida que se incrementa el tamaño n de la lista, el
valor de T(n) crece de manera proporcional a n è T(n)
tiene un orden de magnitud de n.

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

§

§

§

§

§

§

T(n) Î O(f(n)), si $ ctes c y n0 tal que T(n) £ c*f(n), " n³ n0
T(n) Î W(g(n)), si $ ctes c y n0 tal que T(n) ³ c*g(n), " n ³ n0
T(n) Î Q(h(n)), si y sólo T(n) Î O(h(n)) y T(n) Î W(h(n))

Si T(n)ÎO(f(n)) à T(n) nunca crece más rápido que f(n).
Si T(n)ÎW(g(n))à T(n) crece, al menos, al mismo ritmo que
g(n)
Si T(n)ÎQ(h(n))à representa exactamente la tasa de
crecimiento de T(n)

20/1/17

6

Tema 1. Eficiencia de los algoritmos

1. Criterios para medir la eficiencia de un algoritmo
2. Tiempo de ejecución
3. Orden de magnitud
4. Reglas para calcular la complejidad del código
5. Complejidad en código recursivo

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

§

Reglas para el cálculo de complejidad de un algoritmo

1. Si T1(n) Î O(f(n)) y T2(n) Î O (g(n)), entonces:

a) T1(n) + T2(n) Î Max ( O(f(n)), O(g(n)) )
b) T1(n) * T2(n) Î O ( f(n) * g(n) )

2. Si T(x) es un polinomio de grado g à T(x) Î O(xg)

20/1/17

7

20/1/17

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

§

§

§

Definiremos una relación entre los distintos órdenes de magnitud
de las funciones f(n) (siempre válida a partir de un n0
determinado):
O(1) < O(log n) < O(n) < O(n·log n) < O(n2) < O(n3)<...< O(2n) < O(n!) < O(nn)

" n >= n0

Esta notación (O) indica un límite superior de f(n).
Ejemplo: si f(n) es O(n2) à también es O(n3), O(2n)...

Al hallar la complejidad se desprecian las ctes de proporcionalidad.
– Inconveniente: no muy bueno para valores pequeños de la

entrada.

Ejemplo:

T1(n) = 5n3 = O(n3)
T2(n) = 100n2= O(n2)
5n3 / 100n2 = n/20 à para n<20, T1 es mejor.

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

50

45

40

35

30

25

20

15

10

5

0

n
log2n
n·log2n
sqr(n)
n2
n3
2n

0

1

2

3

4

5

6

7

8

9

10

1200

1000

800

600

400

200

0
0

n
log2n
n·log2n
sqr(n)
n2
n3
2n

2

4

6

8

10

12

14

16

18

20

8

20/1/17

n
log2n
n·log2n
sqr(n)
n2
n3
2n

2

4

6

8

10

12

14

16

18

20

Técnicas de Programación Avanzadas (TPA)

Tiempo de ejecución

50

45

40

35

30

25

20

15

10

5

0

n
log2n
n·log2n
sqr(n)
n2
n3
2n

0

1

2

3

4

5

6

7

8

9

10

1200

1000

800

600

400

200

0
0

Tema 1. Eficiencia de los algoritmos

1. Criterios para medir la eficiencia de un algoritmo
2. Tiempo de ejecución
3. Orden de magnitud
4. Reglas para calcular la complejidad del código
5. Complejidad en código recursivo

9

Técnicas de Programación Avanzadas (TPA)

Reglas para calcular la complejidad del código

§ ¿Cómo se traduce todo esto a la hora de calcular la complejidad de

nuestro código?
– Aplicaremos diferentes herramientas
– Dependerán de los elementos o estrategias de programación utilizadas

§ Sentencias simples

– Cada instrucción máquina se ejecuta en un tiempo constante Ki.
– Escogemos como unidad el mayor tiempo Ki.
– Cada sentencia se considera de O(1).
– Válido para manipulaciones (asignaciones, comparaciones, etc.) sobre datos

simples.

§ Composición secuencial:

– Para una secuencia de sentencias à el máximo de todas ellas.

Técnicas de Programación Avanzadas (TPA)

Reglas para calcular la complejidad del código

§

§

§

Selección Condicional (If then else, Case):
–

De entre todos los posibles caminos à el máximo en complejidad.

Repeticiones:
–

å (complej. cuerpo bucle + complej. condición terminación)

Llamadas a otros módulos (procedimientos o funciones):
–

Como si fuesen otras partes del programa

20/1/17

10

Técnicas de Programación Avanzadas (TPA)

Reglas para calcular la complejidad del código

§

Ejemplos:

–

–

–

x = x + 1

for (i=1;i<=N;i++) {

X = X + 1;

}

for (i=1;i<=N;i++) {

for (j=1;j<=N;j++) {
x = x +1;
}

}

O(1)

O(n)

O(n2)

Técnicas de Programación Avanzadas (TPA)

Reglas para calcular la complejidad del código

§Ejemplo:

void burbuja (TElemento A[]) {

for (int i = 1; i <= A.length; i++) {
for (j = A.length; j > i; j--) {

if (A[j-1] > A[j]) {

TElemento temp = A[j-1];
A[j-1] = A[j];
A[j] = temp;

}

}

}

}

20/1/17

11

Técnicas de Programación Avanzadas (TPA)

Reglas para calcular la complejidad del código

§Fórmulas habituales:

n

å

i

1
=
n

å

i

1
=
n

å

i

1
=

1

=

n

1
-

åå

=

i

n

i

1
=

n

i

1
=

1
i

=

log(

n

)

)1

nn
(
+
2
nn
(

i

=

2

i

=

+

n

+

)1

2)(1
6

Técnicas de Programación Avanzadas (TPA)

Reglas para calcular la complejidad del código

§

Recursividad
1. Reducción por SUSTRACCIÓN
2. Reducción por DIVISIÓN

§ Reducción por sustracción

Complejidad
del caso base

T(n) =

c0nk0

si 0 <= n < b

a: número de llamadas recursivas
idénticas en cada invocación del
programa

Complejidad

del caso
general

a·T(n - b) + c1nk
Parte NO
Parte
recursiva
recursiva

si n >=b

n-b: tamaño de los subproblemas
generados

nk:: coste de las instrucciones que no
son llamadas recursivas

T(n) Î Q(nk+1) si a=1
T(n) Î Q(an div b) si a>1

20/1/17

12

Técnicas de Programación Avanzadas (TPA)

Reglas para calcular la complejidad del código

§

Recursividad
1. Reducción por SUSTRACCIÓN
2. Reducción por DIVISIÓN

§ Reducción por división

c0nk0

si 0 <= n < b

T(n) =

a·T(n / b) + c1nk

si n >=b

T(n) Î Q(nk) si a<bk
T(n) Î Q(nk logb n) si a= bk
T(n) Î Q(nlog b a) si a> bk

a: número de llamadas recursivas
idénticas en cada invocación del
programa

n-b: tamaño de los subproblemas
generados

nk:: coste de las instrucciones que no
son llamadas recursivas

20/1/17

13