Complejidad de 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ónComplejidad 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:

ExternosLa 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 demedida 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
COMPLEJIDADTEMPORAL. 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

int ejemplo3 (int n)
{ int i, j;
f (ejemplo3)
j = 2;for (i=0; i ≤ 2000; i++)
j=j*j;
for (i=0; i ≤ n; i++)
{
j = j + j;
j = j - 2;
}
return j;
}

= 1 + 1 · (n + 1) pasos

7

© DLSI (Univ. Alicante)

Tema 1. La eficiencia de los algoritmos

1. Noción de complejidad
COMPLEJIDAD TEMPORAL. Ejemplos

int ejemplo4 (int n)
{ int i, j,k;
f (ejemplo4)
k = 1;
for (i=0; i ≤ n; i++)
for (j=1; j ≤ n; j++)
k = k + k;
return k;
}= 1 + 1 · n · (n + 1) pasos

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 objetivoscontrapuestos
(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...