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 un algoritmo.

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 de datos 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) segundos respectivamente, 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 del caso •

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=0

i=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” Universidad de 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 elevada al número de elementos menos 1 y todo dividido por la razón menos 1”

Universidad de Huelva

Ejemplo

Asignación Suma Comparación 3OE { Asignación Suma Comparación 3OE { Comparacion 4 OE 3 OE 4 OE 2 OE Comp Inc 3OE} Comp Inc 3OE}

Caso Mejor :la condición

será falsa, no se ejecuta (4)a (6). Æ el bucle interno (n–i) iteraciones

Caso Peor :la condición

será verdadera, se ejecuta (4)a (6). Æ el bucle interno (n–i) iteraciones

Universidad de Huelva

Ejemplo II

Asignación Suma Comparación 3OE { Asignación Suma Comparación 3OE { Comparacion 4 OE 3 OE 4 OE 2 OE Comp Inc 3OE} Comp Inc 3OE}

Caso Medio :la condición

será verdadera un

50% de las veces

Universidad de Huelva

Análisis Búsqueda Máximo Busca el máximo en un vector empezando en la posición i hasta la j, por lo que el tamaño de la entrada T(n) = T(j-i) 1 OE Asignación Suma Comparación 3OE { 3 OE + P *1

Comp Inc 3OE} 1 OE

Universidad de Huelva

Análisis Búsqueda Máximo II Asignación 1 OE

Asignación Suma Comparación 3OE { 3 OE + P *1 Asignación 1 OE Comparación Incremento 3OE} Salto 1 OE

Universidad de Huelva

Coste de Intercambio Método que intercambia dos contenidos en el vector dadas sus posiciones. temp:=a[i];

2 OE

a[i]:=a[j];

3OE

a[j]:=temp ;

2 OE

7 OE

Utilizaremos este método y el de búsqueda de máximos y mínimos en un vector para facilitar el análisis de algoritmos de ordenación Universidad de Huelva

Selección En cada paso (i=1...n–1) este método busca el mínimo elemento del subvector a[i..n] y lo intercambia con el elemento en la posición i: Asignación Resta Comparación 3OE { Salto 1OE + Intercambia 7 OE Caso peor Salto 1OE + PosMinimo Comparación Incremento 3OE}

Universidad de Huelva

Burbuja Asignación Resta Comparación 3OE { Asignación suma Comparación 3OE { comparación 4 OE Salto 1OE + Intercambia 7 OE resta 1OE Comparación Incremento 3OE} Comparación Incremento 3OE} }

Universidad de Huelva

Cota Superior – O(f) Asignación Resta Comparación 3OE { Asignación suma Comparación 3OE { comparación 4 OE alto 1OE + Intercambia 7 OE resta 1OE Comparación Incremento 3OE} Comparación Incremento 3OE} }

Universidad de Huelva

Propiedades de O

Universidad de Huelva

Recurrencia T(n) = E(N) donde en E(n) aparece una expresión de T(n) Algoritmos recursivos Se expresa el algoritmo en base a las condiciones iniciales necesarias y una expresión recursiva T(n) = T(n-1) + T(n-2) Para n > 1 T(n) = 1 Para n=1 T(n) =0 Para n= 0

Universidad de Huelva

Ecuaciones Homogeneas

Universidad de Huelva

Raíces distintas

Universidad de Huelva

Raíces distintas II

Universidad de Huelva

Raíces Multiplicidad > 1

Ejemplo:

Universidad de Huelva

No Homogeneas

Universidad de Huelva

Ecuación característica los coeficientes ai y b son números reales, y p(n) es un polinomio en n de grado d Solución

Ejemplo: Torres de Hanoi

Universidad de Huelva

Ecuación generalizada Solución

Ejemplo

Universidad de Huelva

Cambio de variable n es una potencia de 2 (n > 3), T(1) = 1, y T(2) = 6.

b =2 d = 0

Universidad de Huelva