para alumnos. tema 4. recursividad - academia cartagena99 4. recursivi… · asignatura: análisis...

9/15/2016

1

Tema 4. Recursividad

Algorítmica y Complejidad

Universidad Politécnica de MadridEscuela Técnica Superior de Ingeniería de Sistemas Informáticos

1 2 3

Introducción

1

1. Introducción

Algoritmo Recursivo

tipoSalida algoritmoRecursivo(…){…algoritmoRecursivo(…)…

}

Algoritmo

1 2 3

Introducción

1

1. Introducción

Resolución de la complejidad de un algoritmo recursivo

tipoSalida algoritmoRecursivo(…){…algoritmoRecursivo(…)…

}

Algoritmo

T(n) = ….(Ecuación en Diferencias Finitas)

Ecuación de Recurrencia

T(n) (…)

Cálculo del Orden

Asignatura: Análisis Matemático

Resolución de ecuaciones en diferencias finitas:

• Ecuaciones lineales con coeficientes constantes

1 2 3

Introducción

1

1. Introducción

Resolución de la complejidad de un algoritmo recursivo

tipoSalida algoritmoRecursivo(…){…

}


T(n) (…)

Algoritmo


Cálculo del Orden

int factorial (int n){…}

Ejemplos:

int fibonacci (int n){…}

9/15/2016

2

1 2 3

Introducción

1

1. Introducción

Ejemplo: factorial


}


T(n) (…)

Algoritmo


Cálculo del Orden


Ejemplos:


1 2 3

Introducción

1

1. Introducción

Ejemplo: factorial

int factorial (int n){if (n==0)

return 1;else

return n* factorial(n‐1);}


}


T(n) (…)

Algoritmo


Cálculo del Orden

1 2 3

Introducción

1

1. Introducción

Ejemplo: factorial


return 1;else



}


T(n) (…)

Algoritmo


Cálculo del Orden


01 0

1 2 3

Introducción

1

1. Introducción

Ejemplo: factorial


return 1;else



}


T(n) (…)

Algoritmo


Cálculo del Orden


01 0

a (1)

9/15/2016

3

1 2 3

Introducción

1

1. Introducción

Ejemplo: factorial


return 1;else



}


T(n) (…)

Algoritmo


Cálculo del Orden


01 0

T(n ‐ 1) + b

(1)

T(n‐1)

1 2 3

Introducción

1

1. Introducción

Ejemplo: factorial


return 1;else



}


T(n) (…)

Algoritmo


Cálculo del Orden


01 0

Condiciones iniciales

1 2 3

Introducción

1

1. Introducción

Ejemplo: factorial


return 1;else



}


T(n) (…)

Algoritmo


Cálculo del Orden


1

1 2 3

Introducción

1

1. Introducción

Ejemplo: factorial


return 1;else



}


T(n) (…)

Algoritmo


Cálculo del Orden


Resolución de ecuaciones en diferencias finitas

Ecuación lineal con coeficientes constantes

1

9/15/2016

4

1 2 3

Introducción

1

1. Introducción

Ejemplo: factorial


return 1;else



}


T(n) (…)

Algoritmo


Cálculo del Orden T(n) = b∙n + a (n)


1

1 2 3

Introducción

1

1. Introducción



Ejemplo: factorial


}


T(n) (…)

Algoritmo


Cálculo del Orden


Ejemplos:


1 2 3

Introducción

1

1. Introducción

Ejemplo: Fibonacci

int fibonacci (int n){if (n<=1)return 1;

else return fibonacci(n‐1)+fibonacci(n‐2);

}


}


T(n) (…)

Algoritmo


Cálculo del Orden

1 2 3

Introducción

1

1. Introducción

Ejemplo: Fibonacci


}


T(n) (…)

Algoritmo


Cálculo del Orden


11 2 0



}

9/15/2016

5

1 2 3

Introducción

1

1. Introducción

Ejemplo: Fibonacci


}


T(n) (…)

Algoritmo


Cálculo del Orden


11 2 0



}

a (1)

1 2 3

Introducción

1

1. Introducción

Ejemplo: Fibonacci


}


T(n) (…)

Algoritmo


Cálculo del Orden


11 2 1



}T(n ‐ 1) + T(n ‐ 1) + b

(1)

T(n‐2)T(n‐1)

1 2 3

Introducción

1

1. Introducción

Ejemplo: Fibonacci


}


T(n) (…)

Algoritmo


Cálculo del Orden



}


11 2 0

Condiciones iniciales

1 2 3

Introducción

1

1. Introducción

Ejemplo: Fibonacci


}


T(n) (…)

Algoritmo


Cálculo del Orden


1 2



}

9/15/2016

6

1 2 3

Introducción

1

1. Introducción

Ejemplo: Fibonacci


}


T(n) (…)

Algoritmo


Cálculo del Orden



}

Resolución de ecuaciones en diferencias finitas

Ecuación lineal con coeficientes constantes


1 2

1 2 3

Introducción

1

1. Introducción

Ejemplo: Fibonacci


}


T(n) (…)

Algoritmo


Cálculo del Orden



}

Θ1 52

c1>0


1 2

1 2 3

Introducción

1

1. Introducción


}

Algoritmo

Ecuaciones de Recurrencias


T(n) (…)


Cálculo del Orden

• 1

•

•

1 2 3

Ecuación de Recurrencia Simple

2

2. Ecuación de Recurrencia Simple

Recurrencia Simple

1 T(n) = T(n‐1) + b

1 ∈ Θ

Ejemplo 1 0 0

T(0) = b

9/15/2016

7

1 2 3


2


Recurrencia Simple

1

Ejemplo 2

T(n) = T(n‐1) + n

12

∈ Θ

0 0

T(0) = 0

1 2 3


2


Complejidad Algorítmica

Actividad 4.1. Supongamos que tenemos la siguiente ecuación de recurrencia (donde a es una constante):

T(0)=5T(N)=T(N‐1) + 2N+5

Calcula la complejidad de T(N)

2 5 5 1 2 5 5 21

2∈ Θ

1 2 3

Teorema Maestro

3

3. Teorema Maestro


}


T(n) (…)

Algoritmo


Cálculo del Orden

•

•• 1

•

Muy útil para analizar la complejidad en algoritmos basados en el esquema

Divide y Vencerás

1 2 3

Teorema Maestro

3

3. Teorema Maestro

Casos

1er Caso 2º Caso 3er Caso

f(n) O(na)donde a <logq (p)

f(n) (na)donde a >logq (p)

Además se cumple que c<1 n>n0: p∙f(n/q)c∙f(n)

f(n) (na)donde a = logq (p)

ln

p1q>1

9/15/2016

8

1 2 3

Teorema Maestro

3

3. Teorema Maestro

1er Caso






ln

42

5 log

5 log

1 < log2(4)=21er Caso

5n+logn O(n1)log2(4)=2

p1q>1

1 2 3

Teorema Maestro

3

3. Teorema Maestro

2º Caso

3er Caso



42

5

ln

5

2 = log2(4)=22º Caso

5 ∈ Θlog2(4)=2

p1q>1

2º Caso


ln

1 2 3

Teorema Maestro

3

3. Teorema Maestro

2º Caso


ln


1er Caso 44 4

3er Caso

3er Caso



4∈ Ωlog4(4)=1

4

2 > log4(4)=1 4∙f(N/4)=f(N)3er Caso

p1q>1

1 2 3

Teorema Maestro

3

3. Teorema Maestro



T(N)=2∙T(N/2) + aCalcula la complejidad de T(N)

a


∈ Olog2(2)=1

9/15/2016

9

1 2 3

Teorema Maestro

3

3. Teorema Maestro



T(N)=T(N/2) + aCalcula la complejidad de T(N)

log

a


∈ log2(1)=0

1 2 3

Teorema Maestro

3

3. Teorema Maestro


Actividad 4.4. Supongamos que tenemos la siguiente ecuación de recurrencia:

T(N)=T(N/2) + NCalcula la complejidad de T(N)

∈ log2(1)=0

1 > log4(4)=03er Caso2

12

1 2 3

Teorema Maestro

3

3. Teorema Maestro



T(N)=4∙T(N/2) + N2


log


∈ log2(4)=2

1 2 3

Teorema Maestro

3

3. Teorema Maestro



T(N)=8∙T(N/2) + N2 + 2N∙ln NCalcula la complejidad de T(N)

2 ln


2 ln ∈ Olog2(8)=3

9/15/2016

10

1 2 3

Teorema Maestro

3

3. Teorema Maestro



T(N)=4T(N/4) + N2


∈ log4(4)=1

2 > log4(4)=13er Caso 44

416

1 2 3

Teorema Maestro

3

3. Teorema Maestro



T(N)=4∙T(N/2) + N + 2 Calcula la complejidad de T(N)

N + 2

1< log2(4)=21er Caso

2 ∈ Olog2(4)=2

1 2 3

Teorema Maestro

3

3. Teorema Maestro



T(N)=3∙T(N/2) + 3N + ln NCalcula la complejidad de T(N)

.

3

1< log2(3)=1.581er Caso

3 ln ∈ Olog2(3)=1.58

1 2 3

Teorema Maestro

3

3. Teorema Maestro



T(N)=3∙T(N/2) + N2


2> log2(3)=1.583er Caso

∈ Ωlog2(3)=1.58

32

34

9/15/2016

11

1 2 3

Teorema Maestro

3

3. Teorema Maestro

No exhaustividad






ln

Hay casos que NO contempla el TEOREMA MAESTRO !!!

p1q>1

1 2 3

Teorema Maestro

3

3. Teorema Maestro

No exhaustividad: Ejemplo 1






ln


22 log

p1q>1

a < 1 a = 1 a > 1

1 2 3

Teorema Maestro

3

3. Teorema Maestro







ln

p1q>1

a < 1 a = 1 a > 1


22 log

lim→

log lim→

log

∞ f(n) O(na)

1 2 3

Teorema Maestro

3

3. Teorema Maestro


1er Caso 3er Caso



Además se cumple que c<1 n>n0: p∙f(n/q)c∙f(n) ln

p1q>1

a < 1 a > 1


22 log

lim→

log lim→

1

log0 f(n) (n)

2º Caso

f(n) (na)donde a = logq (p)a = 1

9/15/2016

12

1 2 3

Teorema Maestro

3

3. Teorema Maestro

2º Caso

f(n) (na)donde a = logq (p)a = 1


1er Caso


ln

p1q>1

a < 1


22 log



a > 1

lim→

log lim→

1log

0 f(n) (na)

3er Caso

1 2 3

Teorema Maestro

3

3. Teorema Maestro







ln


22

No es una constante

p1q>1

1 2 3

Teorema Maestro

3

3. Teorema Maestro

12 2 log







ln


p1q>1

1 2 3

Teorema Maestro

3

3. Teorema Maestro


1er Caso 2º Caso



ln

Hay casos que NO contempla el TEOREMA MAESTRO !!! 2

2 cos

p1q>1

3er Caso



a > 0

9/15/2016

13

1 2 3

Teorema Maestro

3

3. Teorema Maestro


1er Caso 2º Caso



ln

Hay casos que NO contempla el TEOREMA MAESTRO !!! 2

2 cos

p1q>1

3er Caso



lim→

2 coslim→

2 cos ∞ f(n) (na) a > 0Para a<1

22 cos

2 2 cos c3/2

Para n=2+4k

para alumnos. tema 4. recursividad - academia cartagena99 4. recursivi… · asignatura: análisis...

Documents