Biometria

Complejidad de Algoritmos
Tema 5

Universidad de Huelva

Introducción
• Un algoritmo es una secuencia de instrucciones que
resuelve un problema
• Puede tener diferentes implementaciones
• Para comparar las diferentes formas (algoritmos) de
resolver un problema debe ser posible medirlos : Tiempo y
memoria .
• La medida de la eficiencia requiere determinar la
complejidad de unalgoritmo.

Universidad de Huelva

Factores del tiempo
• Datos de entrada:la dimensión del vector a ordenar o el
tamaño de las matrices a multiplicar
• Calidad del código generado por el compilador
• Arquitectura del procesador (cisc , risc)
• Complejidad intrínseca del algoritmo
• Medidas:
– A priori (Acotación teórica del algoritmo)
– A posteriori (empírica o práctica) para un conjunto dedatos y
para un ordenador concreto.

Universidad de Huelva

Factores del tiempo II
–La unidad de tiempo no puede ser concreta, no existe un ordenador estándar
al que puedan hacer referencia todas las medidas.
T(n) el tiempo de ejecución para una entrada de tamaño n.

Principio de Invarianza
Dado un algoritmo y dos implementaciones suyas I1 e I2, que tardan T1(n) y
T2(n) segundosrespectivamente, el Principio de Invarianza afirma que
existe una constante real c > 0 y un número natural n0 tales que para todo n
>= n0 se verifica que T1(n) 5 AND 5 == 3)
• El acceso a vectores y matrices.
• Ejemplos :
a++
b = a*5 – Vector[2*2]
b += suma(a,b3

2 OE
5 OE
4 OE
6 OE

(=,+)
(=,*,- ,[],*)
(=,+,salto,)

Universidad de Huelva

Universidad de Huelva

Análisis delcaso
•

caso mejor :línea (1) y (2) sólo la primera mitad
de la condición: 2 OE
(expresiones se evalúan de izquierda a derecha, y con
“cortocircuito” )
+ (5) a (7). T(n)=1+2+3=6.

•

caso peor:
– (1)
– bucle se repite n–1 veces hasta que se cumple la
segunda condición
– (5) hasta línea (7).
– Cada iteración del bucle compuesta (2) y (3), +
ejecución adicional de la línea (2)Universidad de Huelva

Análisis del caso II

Universidad de Huelva

Calculo de OE II
- CASE C OF v1:S1|v2:S2|...|vn:Sn END
T = T(C)+max{T(S1),T(S2),...,T(Sn)}.
- IF C THEN S1 ELSE S2 END
T = T(C) + max{T(S1),T(S2)}.
_ WHILE C DO S END
T = T(C) + (nº iteraciones)*(T(S) + T(C)).
ojo tanto T(C) como T(S) pueden variar en cada iteración
Para resto de sentencias iterativas (FOR,etc...)basta expresarlas como
un bucle WHILE.

Universidad de Huelva

Fórmulas I
Sumatorias
1) La sumatoria de una suma es igual a la suma de las sumatorias:

∑

a+b=

∑

a +

∑

b

2) Cuando el cuerpo de la sumatoria es independiente de los índices, el valor es el número de valores
diferentes que toma el índice multiplicado por el valor del cuerpo:
n −1

∑

a = a.n

i =0
n −1∑
i =0

n −1

a + f(i) =

∑
i =0

n −1

a+

∑
i =0

n −1

f(i) = a.n +

∑

f(i)

i =0

Universidad de Huelva

Fórmulas II
3) Cuando el cuerpo de la sumatoria se puede expresar como una constante independiente de los índices
multiplicada por una expresión, el valor es el valor de la constante multiplicada por la sumatoria de la
expresión:
n−1

n−1

i=0i=0

∑ af(i) = a ∑ f(i)
4) Suma de los valores de una progresión aritmética: Ej:(1+2+3+4+5),(4+6+8+10) ,(2+5+8+11+14)
∆ = incremento
a0 = primer elemento
an-1 = último elemento
n = número de elementos
progresión aritmética: an = a0 + ∆n
n−1

∑ a = ((a +a
i

i

n-1)n)/2

i=0

“El primer elemento más el último, multiplicado por el número de elementos y dividido por 2”
Universidadde Huelva

Formulas III
5) Suma de los valores de una progresión geométrica: Ej:(1+2+4+8+16), (2+6+18+54)
Π = razón
a0 = primer elemento
n = número de elementos
progresión geométrica: an = a0 Π n
(r-1)(1 + r + ... + rn-1) = rn - 1
n −1

∑
i =0

n −1

ai =

∑
i =0

n −1

i

a0 Π = a0

∑

Π i = a0(Π n-1)/( Π-1)

i =0

“El primer elemento multiplicado por la razón...