Teorema Mestre 542y3u

Recorrˆencias (continua¸c˜ao) Fernando Lobo Algoritmos e Estrutura de Dados II

1 / 15

Teorema Mestre

I

Serve para resolver grande parte das recorrˆencias da forma: n T (n) = aT + f (n) b onde a ≥ 1, b > 1, f (n) > 0, ∀n > n0 .

I

Existem 3 casos. Compara-se

nlogb a com f (n)

2 / 15

Teorema Mestre I

Caso 1:

f (n) = O nlogb a− para um > 0 (f(n) ´e polinomiamente inferior a nlogb a )

Solu¸c˜ao:

T (n) = Θ(nlogb a )

I

Intuitivamente: custo ´e dominado pelas folhas da ´arvore de recorrˆencia. ———————————————————————– Caso 2: f (n) = Θ nlogb a Solu¸c˜ao:

T (n) = Θ(nlogb a lg n) Intuitivamente: custo ´e idˆentico em cada n´ıvel da ´arvore de recorrˆencia. 3 / 15

Teorema Mestre: Caso 1 Caso 1:

f (n) = O nlogb a− para um > 0 (f (n) ´e polinomiamente inferior a nlogb a )

Solu¸c˜ao:

T (n) = Θ(nlogb a )

Intuitivamente: custo ´e dominado pelas folhas da ´arvore de recorrˆencia.

4 / 15

Teorema Mestre: Caso 2

Caso 2:

f (n) = Θ

nlogb a



Solu¸c˜ao:

T (n) = Θ(nlogb a lg n)

Intuitivamente: custo ´e idˆentico em cada n´ıvel da ´arvore de recorrˆencia.

5 / 15

Teorema Mestre: Caso 3 Caso 3: I

f (n) = Ω nlogb a+ para um > 0 (f (n) ´e polinomiamente superior a nlogb a )

I

af ( bn ) ≤ cf (n) para um c < 1 e para todo n > n0 (Chama-se a isto Condi¸c˜ao de Regularidade)

Solu¸c˜ao:

T (n) = Θ(f (n)) Intuitivamente: custo ´e dominado pela ra´ız da ´arvore de recorrˆencia. A condi¸c˜ao de regularidade ´e sempre verdadeira quando f (n) = nk . 6 / 15

Teorema Mestre Exemplo 1 4T ( n2 ) + n

T (n) = a

b

Comparar nlogb a

f (n)

com

nlog2 4 = n2

Caso 1: f (n) = n = O(n2− )

f (n) n

para = 1 , logo

T (n) = Θ(n2 )

7 / 15

Teorema Mestre

Exemplo 2 T (n) =

4T ( n2 ) + n2 f(n)

nlogb a = nlog2 4 = n2

n2

Caso 2: f (n) = n2 = Θ(n2 ), logo T (n) = Θ(n2 lg n)

8 / 15

Teorema Mestre Exemplo 3 T (n) =

4T ( n2 ) + n3 f(n)

nlogb a = nlog2 4 = n2

n3

Caso 3: I f (n) = n3 = Ω(n2+ ) para = 1 I Condi¸ c˜ao de Regularidade: n 3 4n3 3 4 ≤ cn ⇔ ≤ cn3 2 8 1 3 1 ⇔ n ≤ cn3 ,basta escolher c ≥ 2 2 I

N˜ao era necess´ario mostrar a Condi¸c˜ao de Regularidade porque f (n) ´e polinomial.

Logo, T (n) = Θ(n3 ) 9 / 15

Teorema Mestre

Exemplo 4 T (n) =

4T ( n2 ) +

n2 lg n

f(n) nlogb a = nlog2 4 = n2

n2 lg n

O Teorema Mestre n˜ao ´e aplic´avel!

10 / 15

Teorema Mestre (intui¸c˜ao) I

A demonstra¸c˜ao formal est´a no livro [CLRS].

I

Este formato de T (n) aparece em problemas de D&C:

T (n) =

n´ umero de subproblemas

Θ(1) , se n = 1 aT ( bn ) + f (n) , se n > 1 tamanho de cada subproblema

onde a ≥ 1, b > 1

trabalho n˜ao recursivo

——————————————– T (n) = f (n) a vezes

T

n b



n b

T



.

.

T

n b

11 / 15

Teorema Mestre (intui¸c˜ao)

Iterando:

T (n) =

f (n) a vezes

f T

n b2



.

n b

a vezes

.

.

. . .

. . .

f .

.

n b

a vezes

. T

n b2



12 / 15

Teorema Mestre (intui¸c˜ao) Iterando mais vezes: T (n) =

f (n)

f(n) a

h = logb n

f n

f

b2

.

n b



. . .

. . .

n b

f

a

.

.

.

.



af ( bn )

a



a2 f ( bn2 )

T(1)

ah Θ(1) —————– Total

n b2

. f

. . . . . . . . . . . . . . . . . . . . . . . . T(1)

T(1)

T(1)

. . . . . . . . . . T(1)

T(1)

13 / 15

I

A altura da ´arvore ´e h = logb n

I

No u ´ltimo n´ıvel temos ah subproblemas de tamanho 1. ah Θ(1) = alogb n Θ(1) = nlogb a Θ(1) = Θ(nlogb a )

Soma n´ıvel por n´ıvel: Total = f (n) + af |

n n h−1 +a f + .. + a f + Θ(nlogb a ) 2 h−1 b b{z b }

n

2

logb n−1

T (n) =

X i=0

i

af

n bi

+

Θ(nlogb a )

14 / 15

Se f (n) ´e polinomial, i.e., f (n) = nk para algum k fixo, resulta: logb n−1

T (n) =

X i=0 k

= n ×

a

i

n k bi

+ Θ(nlogb a )

logX b n−1

| i=0

a i bk {z }

+ Θ(nlogb a )

p.g .com logb n parcelas e r =

a bk

Daqui obtemos: I

Se r > 1 logb a > k ⇒ T (n) = Θ(nlogb a )

I

Se r = 1 logb a = k ⇒ T (n) = Θ(nk logb n)

I

(Caso 1) (Caso 2)

Se r < 1 logb a < k ⇒ T (n) = Θ(nk )

(Caso 3) 15 / 15