PDF de programación - Tema1 - La eficiencia de los algoritmos

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

TEMA 1

La eficiencia de los algoritmos

PROGRAMACIÓN Y ESTRUCTURAS DE

DATOS

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

La eficiencia de los algoritmos

1. Noción de complejidad

Complejidad temporal, tamaño del problema y paso

2. Cotas de complejidad

Cota superior, inferior y promedio

3. Notación asintótica

Ο, Ω, Θ

4. Obtención de cotas de complejidad

2

1

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

1. Noción de complejidad

DEFINICIÓN

Cálculo de complejidad: determinación de dos parámetros o
funciones de coste:

Complejidad espacial : Cantidad de recursos espaciales ( de
almacén) que un algoritmo consume o necesita para su
ejecución
Complejidad temporal : Cantidad de tiempo que un algoritmo
necesita para su ejecución

Posibilidad de hacer

Valoraciones

el algoritmo es: “bueno”, “el mejor”, “prohibitivo”

Comparaciones

el algoritmo A es mejor que el B

3

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

1. Noción de complejidad

COMPLEJIDAD TEMPORAL

Factores de complejidad temporal:

Externos

La máquina en la que se va a ejecutar
El compilador: variables y modelo de memoria
La experiencia del programador

Internos

El número de instrucciones asociadas al algoritmo

Complejidad temporal : Tiempo(A) = C + f (T)

C es la contribución de los factores externos
(constante)
f(T) es una función que depende de T (talla o
tamaño del problema)

4

2

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

1. Noción de complejidad

COMPLEJIDAD TEMPORAL

Talla o tamaño de un problema:

Valor o conjunto de valores asociados a la entrada del
problema que representa una medida de su tamaño
respecto de otras entradas posibles

Paso de programa:

Secuencia de operaciones con contenido semántico cuyo
coste es independiente de la talla del problema
Unidad de medida de la complejidad de un algoritmo

Expresión de la complejidad temporal:

Función que expresa el número de pasos de programa que
un algoritmo necesita ejecutar para cualquier entrada
posible (para cualquier talla posible)
No se tienen en cuenta los factores externos

5

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

1. Noción de complejidad

COMPLEJIDAD TEMPORAL. Ejemplos

int ejemplo1 (int n)
{

n+ = n;
return n;

f (ejemplo1) = 1 pasos

}

}

int ejemplo2 (int n)
{

int i;
for (i=0; i ≤ 2000; i++)
n+ = n;
return n;

f (ejemplo2) = 1 pasos

6

3

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

1. Noción de complejidad

COMPLEJIDAD TEMPORAL. Ejemplos

f (ejemplo3) = 1 + 1 · (n + 1) pasos

int ejemplo3 (int n)
{

int i, j;
j = 2;
for (i=0; i ≤ 2000; i++)
for (i=0; i ≤ n; i++)
{

j=j*j;

j = j + j;
j = j - 2;

}
return j;

}

7

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

1. Noción de complejidad

COMPLEJIDAD TEMPORAL. Ejemplos

f (ejemplo4) = 1 + 1 · n · (n + 1) pasos

int ejemplo4 (int n)
{

int i, j,k;
k = 1;
for (i=0; i ≤ n; i++)

for (j=1; j ≤ n; j++)

k = k + k;

return k;

int ejemplo5 (int n)
{

int i, j,k;
k = 1;
for (i=0; i ≤ n; i++)

for (j=i; j ≤ n; j++)

k = k + k;

return k;

}

}

f (ejemplo5) = 1 + Σi=0..n(Σj=i..n 1) pasos

8

4

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

1. Noción de complejidad

CONCLUSIONES

Sólo nos ocuparemos de la complejidad temporal
Normalmente son objetivos contrapuestos

(complejidad temporal <--> complejidad espacial)

Cálculo de la complejidad temporal:

a priori: contando pasos
a posteriori: generando instancias para distintos valores y
cronometrando el tiempo

Se trata de obtener la función. Las unidades de medida (paso, sg,
msg, ...) no son relevantes (todo se traduce a un cambio de escala)
El nº de pasos que se ejecutan siempre es función del tamaño (o talla)
del problema

9

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

2. Cotas de complejidad

INTRODUCCIÓN

Dado un vector X de n números naturales y dado un número
natural z:

encontrar el índice i : Xi = z
Calcular el número de pasos que realiza

funcion BUSCAR (var X:vector[N]; z: N): devuelve N
var i:natural fvar;
comienzo
i:=1;
mientras (i ≤⏐X⏐) ∧ (Xi≠z) hacer
i:=i+1;
fmientras
si i= ⏐X⏐+1 entonces devuelve 0 (*No encontrado*)

si_no devuelve i

fin

10

5

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

2. Cotas de complejidad

EL PROBLEMA

11

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

2. Cotas de complejidad
LA SOLUCIÓN: cotas de complejidad

Cuando aparecen diferentes casos para una misma talla
genérica n, se introducen las cotas de complejidad:

Caso peor: cota superior del algoritmo → Cs(n)
Caso mejor: cota inferior del algoritmo→ Ci(n)
Término medio: cota promedio → Cm(n)

Todas son funciones del tamaño del problema (n)
La cota promedio es difícil de evaluar a priori

Es necesario conocer la distribución de la probabilidad de
entrada
No es la media de la inferior y de la superior (ni están todas
ni tienen la misma proporción)

12

6

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

2. Cotas de complejidad
EJERCICIO: cotas superior e inferior

funcion BUSCAR (var X:vector[N]; z: N): devuelve N
var i:natural fvar;
comienzo
i:=1;
mientras (i ≤⏐X⏐) ∧ (Xi≠z) hacer
i:=i+1;
fmientras
si i= ⏐X⏐+1 entonces devuelve 0 (*No encontrado*)

si_no devuelve i

fin

Talla del problema: nº de elementos de X: n
¿Existe caso mejor y caso peor?

Caso mejor: el elemento está el primero: X1=z → ci(n) = 1
Caso peor: el elemento no está: ∀i 1≤ i ≤ |X|, Xi ≠ z → cs(n) = n+1

13

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

2. Cotas de complejidad
EJERCICIO: cotas superior e inferior

Complejidad función Buscar

18
16
14
12
10
8
6
4
2
0

Cota Superior

Ci(n)=1
Cs(n)=n+1

¿Cota promedio?

1

5

10

15

Cota Inferior

14

7

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

2. Cotas de complejidad

CONCLUSIONES

La cota promedio no la calcularemos. Sólo se hablará de complejidad
por término medio cuando la cota superior y la inferior coinciden
El estudio de la complejidad se hace para tamaños grandes del
problema por varios motivos:

Los resultados para tamaños pequeños o no son fiables o
proporcionan poca información sobre el algoritmo
Es lógico invertir tiempo en el desarrollo de un buen algoritmo
sólo si se prevé que éste realizará un gran volumen de
operaciones

A la complejidad que resulta de tamaños grandes de problema se le
denomina complejidad asintótica y la notación utilizada es la notación
asintótica

15

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

3. Notación asintótica

INTRODUCCIÓN

Notación matemática utilizada para representar la
complejidad espacial y temporal cuando n → ∞
Se definen tres tipos de notación:

Notación O (big-omicron) ⇒ caso peor
Notación Ω (omega) ⇒ caso mejor
Notación Θ (big-theta) ⇒ caso promedio

16

8

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

3. Notación asintótica
Teorema de la escala de complejidad

Ο ⊂ Ο

(1)

n
(lg lg )

⊂ Ο

n
(lg )

⊂ Ο

(lg

a

1
>

n

)

⊂ Ο

(

n

)

⊂

O n
( )

⊂

⊂ Ο

n
n
( lg )

⊂ Ο

(

n

2

)

⊂ ⊂ Ο

L

a

>

2

(

n

)

⊂ Ο

(2 )
n

⊂ Ο

n
( !)

⊂ Ο

(

n

n

)

f(n) + g(n) + t(n) ∈ O(Max(f(n), g(n), t(n)))
Ejemplos:

– n + 1 pertenece a O(n)
– n2 + log n pertenece a O(n2)
– n3 + 2n + nlogn pertenece a O(2n)

Válido para Notación Ω y Notación Θ

17

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

3. Notación asintótica
NOTACIÓN O: escala de complejidad

Complejidad

n3
2n

n = 32
3 seg.
5 días

n = 64
26 seg.

58⋅106 años

Tiempos de respuesta para dos valores de
la talla y complejidades n3 y 2n.
(paso = 0’1 mseg.)

Queda clara la necesidad del cálculo de complejidad
función POT_2 (n: natural): natural

Coste lineal

1 seg.

Coste exponencial

miles de años

18

9

opción

fopción

ffunción

n = 1: devuelve 2
n > 1: devuelve 2 * POT_2(n-1)

función POT_2 (n: natural): natural

n = 1: devuelve 2
n > 1: devuelve POT_2(n-1)+POT_2(n-1)

opción

fopción

ffunción

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

4. Obtención de cotas de complejidad

INTRODUCCIÓN

Etapas para obtener las cotas de complejidad:
1. Determinación de la talla o tamaño (de la instancia ) del

problema

2. Determinación del caso mejor y peor: instancias para las que

el algoritmo tarda más o menos

No siempre existe mejor y peor caso ya que existen algoritmos que se
comportan de igual forma para cualquier instancia del mismo tamaño

3. Obtención de las cotas para cada caso. Métodos:

cuenta de pasos
relaciones de recurrencia (funciones recursivas)

19

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

4. Obtención de cotas de complejidad

INTRODUCCIÓN

función FACTORIAL (n:natural): natural

La talla es n y no existe caso mejor ni peor

función BUSCA (v: vector[natural]; x:natural)

La talla es n=|v|
caso mejor: instancias donde x está en v[1]
caso peor: instancias donde x no está en v

Se trata de delimitar con una región
el tiempo que tarda un algoritmo
en ejecutarse

o
p
m
e
i
t

caso peor

promedio

caso mejor

n=64

tamaño

20

10

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

4. Obtención de cotas de complejidad

Ejemplos

Cálculo del máximo de un vector

funcion MÁXIMO (var v : vector[n]; n:entero) : entero
var i, max : entero fvar
comienzo

max:=v[1]
para i:=2 hasta n hacer
fpara
devuelve max

si v[i]>max entonces max:=v[i] fsi

fin

determinar la talla del problema: n=tamaño del vector

mejor caso

c

i

1
= +

peor caso

c

s

1
= +

n

∑

i=2

1 1 (
= +

n

− + = ∈Ω

2 1)

n

n

∑

i=2

2 1 (
= +

n

− +

2 1)·2 2

=

n

n
( )

⎫
⎪
⎪∈Θ⎬
⎪
n
1
( )
− ∈Ο ⎪⎭

n
( )

21

©DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

4. Obtención de cotas de complejidad

Ejemplos

Búsqueda de un elemento en un vector o