Análise de Algoritmos - Solução de Recorrências

Analise de Algoritmos

Solução de recorrências

–p. 1/44

Recorrências

Uma recorrência é uma expressão que dá o valorde uma função em termos dos valores "anteriores"da mesma função.

– p. 2/44

Recorrências

Uma recorrência é uma expressão que dá o valorde uma função em termos dos valores "anteriores"da mesma função.

Para analisar o consumo de tempo de umalgoritmo recursivo é necessário resolver umarecorrência.

– p. 2/44

Recorrências

O exemplo clássico de recorrência, provavelmenteo mais famoso, é a fórmula de Fibonacci:

F (n) =

!"""#

"""$

0 se n = 0

1 se n = 1

F (n! 1) + F (n! 2) se n " 2

– p. 3/44

Recorrências

O exemplo clássico de recorrência, provavelmenteo mais famoso, é a fórmula de Fibonacci:

F (n) =

!"""#

"""$

0 se n = 0

1 se n = 1

F (n! 1) + F (n! 2) se n " 2

Uma “fórmula fechada” para F (n) é dada por:

F (n) =1#5

%1 +

#5

2

&n

! 1#5

%1!

#5

2

&n

– p. 3/44

Recorrências

Um outro exemplo clássico de recorrência é:

F (n) =

!#

$1 se n = 0

n.F (n! 1) se n " 1

– p. 4/44

Recorrências

Um outro exemplo clássico de recorrência é:

F (n) =

!#

$1 se n = 0

n.F (n! 1) se n " 1

Uma fórmula fechada para F (n) é dada por:

F (n) = n.F (n! 1)

= n.(n! 1).F (n! 2) = · · · == n.(n! 1).(n! 2) . . . 2.1.1

= n!– p. 4/44

Recorrências

Resolver uma recorrência é encontrar uma“fórmula fechada” que dê o valor da funçãodiretamente em termos do seu argumento.

– p. 5/44

Recorrências - busca binária

Vamos analisar novamente o consumo de tempodo algoritmo da busca binária.

– p. 6/44


Vamos analisar novamente o consumo de tempodo algoritmo da busca binária. Em cada iteração,o algoritmo descarta metade do vetor.

– p. 6/44


Vamos analisar novamente o consumo de tempodo algoritmo da busca binária. Em cada iteração,o algoritmo descarta metade do vetor. Sedenotamos por T (n) o número máximo deiterações realizadas pela busca binária sobre umvetor com n elementos,

– p. 6/44


Vamos analisar novamente o consumo de tempodo algoritmo da busca binária. Em cada iteração,o algoritmo descarta metade do vetor. Sedenotamos por T (n) o número máximo deiterações realizadas pela busca binária sobre umvetor com n elementos, a função T (n) pode serexpressa pela seguinte recorrência:

T (n) = T ('n2

() + 1, T (1) = 1

– p. 6/44


Para obter uma solução, supomos inicialmente quen = 2k.

– p. 7/44


Para obter uma solução, supomos inicialmente quen = 2k.

T (n) = T)n2

*+ 1

=)T) n

22

*+ 1

*+ 1 = T

) n

22

*+ 2

=)T) n

23

*+ 1

*+ 2 = T

) n

23

*+ 3

= · · ·

= T) n

2k

*+ k = k + 1 = log n+ 1

– p. 7/44


Podemos agora tentar mostrar queT (n) $ log n+ 1, %n " 1, por indução em n.

– p. 8/44



Para n = 1, T (1) = 1 = log 1 + 1

– p. 8/44



Para n = 1, T (1) = 1 = log 1 + 1

Para n > 1, temos

– p. 8/44



Para n = 1, T (1) = 1 = log 1 + 1

Para n > 1, temos

T (n) = T ('n2

() + 1

$ (log('n2

() + 1) + 1

$ log)n2

*+ 2 = (log n! 1) + 2

= log n+ 1

– p. 8/44

Recorrências - Exemplo

Consideremos a recorrência

T (n) = 2T ('n2

() + n! 1, T (1) = 1

– p. 9/44



T (n) = 2T ('n2

() + n! 1, T (1) = 1

Podemos conjecturar que T (n) $ n2 e tentar provarpor indução em n.

– p. 9/44



T (n) = 2T ('n2

() + n! 1, T (1) = 1


T (1) = 1 $ 12

– p. 9/44



T (n) = 2T ('n2

() + n! 1, T (1) = 1


T (1) = 1 $ 12

T (2) = 2T (1) + 1 = 3 < 22

– p. 9/44


Para n " 3, temos

– p. 10/44


Para n " 3, temos

T (n) = 2T ('n2

() + n! 1

$ 2'n2

(2+ n! 1

$ 2)n2

*2+ n! 1

$ n2

2+ n! 1

$ n2

2+

n2

2= n2, %n > 0

– p. 10/44


Será n2 uma boa estimativa para T (n)?

–p. 11/44


Será n2 uma boa estimativa para T (n)?Será que conseguimos provar que T (n) $ cn, paraalguma constante c > 0 e n " n0?

–p. 11/44


Será n2 uma boa estimativa para T (n)?Será que conseguimos provar que T (n) $ cn, paraalguma constante c > 0 e n " n0? Vamos tentar.

– p. 11/44


T (n) = 2T ('n2

() + n! 1

$ 2c'n2

(+ n! 1

$ 2c)n2

*+ n! 1

$ cn+ n! 1 ! cn

Para qualquer c > 0.

– p. 12/44


T (n) = 2T ('n2

() + n! 1

$ 2c'n2

(+ n! 1

$ 2c)n2

*+ n! 1

$ cn+ n! 1 ! cn

Para qualquer c > 0. Logo,

T (n) ! cn

– p. 12/44


E que tal T (n) $ n log2 n+ 1?

–p. 13/44



T (1) = 1 = 1 log 1 + 1

– p. 13/44



T (1) = 1 = 1 log 1 + 1

T (2) = 2T (1) + 1 = 3 = 2 log 2 + 1

– p. 13/44



T (1) = 1 = 1 log 1 + 1

T (2) = 2T (1) + 1 = 3 = 2 log 2 + 1

Vamos então tentar mostrar que

T (n) $ n log2 n+ 1

para n " 1.

– p. 13/44


T (n) = 2T ('n2

() + n! 1

$ 2('n2

(log

'n2

(+ 1) + n! 1

$ 2()n2

*log

)n2

*+ 1) + n! 1

= n(log n! 1) + n+ 1 = n log n+ 1

– p. 14/44


T (n) = 2T ('n2

() + n! 1

$ 2('n2

(log

'n2

(+ 1) + n! 1

$ 2()n2

*log

)n2

*+ 1) + n! 1

= n(log n! 1) + n+ 1 = n log n+ 1

Portanto,T (n) $ n log n+ 1

para n " 1.– p. 14/44

Recorrências

Os exemplos anteriores mostram que a solução deuma recorrência pode ser obtida:

1. Desenvolvendo (ou “desenrolando”) arecorrência.

2. Estimando a solução e provando o resultadopor indução.

Estas duas formas conjuntas recebem o nome demétodo da substituição.

– p. 15/44



T (n) = T ('n2

() + T (

+n2

,) + 1, T (1) = 1

– p. 16/44



T (n) = T ('n2

() + T (

+n2

,) + 1, T (1) = 1

Podemos conjecturar que T (n) $ cn e tentar provarpor indução em n.

– p. 16/44



T (n) = T ('n2

() + T (

+n2

,) + 1, T (1) = 1

Podemos conjecturar que T (n) $ cn e tentar provarpor indução em n. É comum partimos logo paraanalisar o caso geral, pois a base geralmente podeser acertada.

– p. 16/44


T (n) = T ('n2

() + T (

+n2

,) + 1

$ c'n2

(+ c

+n2

,+ 1

= cn+ 1

O que não implica que T (n) $ cn.

– p. 17/44


T (n) = T ('n2

() + T (

+n2

,) + 1

$ c'n2

(+ c

+n2

,+ 1

= cn+ 1

O que não implica que T (n) $ cn.Importante: precisamos provar a forma exata dahipótese indutiva.

– p. 17/44


Uma forma de contornar este problema é subtrairum termo de ordem menor. Por exemplo, tomemosagora T (n) $ cn! 1.

– p. 18/44



T (n) = T ('n2

() + T (

+n2

,) + 1

$ (c'n2

(! 1) + (c

+n2

,! 1) + 1

$ cn! 1

para qualquer c positivo.

– p. 18/44



T (n) = T ('n2

() + T (

+n2

,) + 1

$ (c'n2

(! 1) + (c

+n2

,! 1) + 1

$ cn! 1

para qualquer c positivo. Tomando c = 2, temosT (1) = 1 $ 2(1)! 1. Logo, T (n) $ 2n! 1.

– p. 18/44

Recorrências - Exercícios

1. Resolva a recorrência T (n) = T (-n2

.) + 7n+ 2,

T (1) = 1.2. Mostre que a solução de T (n) = T (n! 1) + n é O(n2).3. Mostre que a solução de T (n) = T (

/n2

0) + 1 é O(log n).

4. Mostre que a solução de T (n) = 2T (-n2

.+ 17) + n é

O(n log n).5. Resolva a recorrência T (n) = 3T (

-n2

.) + n, T (1) = 1.

6. Resolva a recorrência T (n) = 3T (-n3

.) + 1, T (1) = 1.

7. Mostre que a solução de T (n) = 3T1n2

2+ n é O(nlog2 3).

8. Mostre que a solução de T (n) = 4T1n2

2+ n é O(n2).

– p. 19/44


Identidades úteis

– p. 20/44

Identidades úteis

Apresentamos a seguir algumas igualdades edesigualdades que são úteis na análise algoritmos.

– p. 21/44

Identidades úteis

Apresentamos a seguir algumas igualdades edesigualdades que são úteis na análise algoritmos.

Serie aritmetica: Se ai = ai!1 + c, onde c é umaconstante, então

a1 + a2 + a3 + · · ·+ an =n(an + a1)

2

– p. 21/44

Série geométrica

Se ai = cai!1, onde c &= 1 é uma constante, então

a1 + a2 + a3 + · · ·+ an =a1(cn ! 1)

c! 1

Se 0 < c < 1, então'3

i=1

ai =a1

1! c

– p. 22/44

Soma de quadrados

n3

i=1

i2 =n(n+ 1)(2n + 1)

6

– p. 23/44

Logaritmos

logb a =logc a

logc b

aloga x = x

– p. 24/44

Aproximação de Stirling

n! =#2!n

)ne

*n(1 +O(

1

n))

Em particular, a aproximação de Stirling implicaque

log(n!) = !(n log n)

– p. 25/44


Árvore de recursão

–p. 26/44

Árvore de recursão

Árvore de recursão é um método muito útil paraestimar a solução de uma recorrência. Uma vezobtida a solução, utilizamos o método anterior paraprová-la formalmente.A idéia da árvore de recursão é tentar representaro desenvolvimento da recorrência por um diagrama(geralmente uma árvore) onde cada nó representaum subproblema, e somar os custos por nível.

– p. 27/44

Exemplo 1

Consideremos a recorrência T (n) = 2T1(n2)

2+ n

– p. 28/44

Exemplo 2

T (n) = T1(n3)

2+ T

1(2n3 )

2+ n

– p. 29/44

Exemplo 3

T (n) = 3T1(n2)

2+ n2

– p. 30/44

ExercíciosUse árvore de recursão para determinar um limite superiorpara as recorrências abaixo, e depois prove o resultadousando indução ou substituição.1. T (n) = T (n/4) + T (n/2) + n2

2. T (n) = 3T1(n4 )

2+ n

3. T (n) = 4T1n2 + 2

2+ n

4. T (n) = T (n! a) + T (a) + cn

– p. 31/44


Método mestre

–p. 32/44

Método mestre

O método mestre fornece uma receita para asolução de recorrências da forma

T (n) = aT (n/b) + f(n)

onde a " 1 e b > 1 são constantes e f(n) é umafunção assintóticamente positiva.

– p. 33/44

Método mestre

Considere a recorrência

T (n) = aT (n/b) + f(n)

onde a " 1 e b > 1 são constantes, f(n) é umafunção assintóticamente positiva, e n/b pode ser(n/b) ou *n/b+. Então

1. Se f(n) = O(nlogb a!!) para alguma constante" > 0 então T (n) = !(nlogb a)

– p. 34/44

Método mestre

Considere a recorrência

T (n) = aT (n/b) + f(n)

onde a " 1 e b > 1 são constantes, f(n) é umafunção assintóticamente positiva, e n/b pode ser(n/b) ou *n/b+. Então

1. Se f(n) = O(nlogb a!!) para alguma constante" > 0 então T (n) = !(nlogb a)

2. Se f(n) = !(nlogb a) então T (n) = !(nlogb a log n)

– p. 34/44

Método mestre

3. Se f(n) = "(nlogb a+!) para alguma constante" > 0, e se af(n/b) $ cf(n) para algumaconstante c < 1 e n suficientemente grande,então T (n) = !(f(n))

– p. 35/44

Método mestre

T (n) = aT (n/b) + f(n)

T (n) Se

!(nlogb a) f(n) = O(nlogb a!!)

!(nlogb a log n) f(n) = !(nlogb a)

!(f(n)) f(n) = "(nlogb a+!)

e af(n/b) $ cf(n), c < 1

– p. 36/44

Método mestre - Exemplo 1

T (n) = 9T (n/3) + n

– p. 37/44


T (n) = 9T (n/3) + n

a = 9, b = 3 e f(n) = n

– p. 37/44


T (n) = 9T (n/3) + n

a = 9, b = 3 e f(n) = n

nlogb a = nlog3 9 = n2

– p. 37/44


T (n) = 9T (n/3) + n

a = 9, b = 3 e f(n) = n


Logo, f(n) = O(nlogb a!!), onde " = 1

– p. 37/44


T (n) = 9T (n/3) + n

a = 9, b = 3 e f(n) = n


Logo, f(n) = O(nlogb a!!), onde " = 1

Pelo Caso 1, T (n) = !(n2).

– p. 37/44


T (n) = T (2n/3) + 1

– p. 38/44


T (n) = T (2n/3) + 1

a = 1, b = 3/2 e f(n) = 1

– p. 38/44


T (n) = T (2n/3) + 1

a = 1, b = 3/2 e f(n) = 1

nlogb a = nlog3/2 1 = n0 = 1

– p. 38/44


T (n) = T (2n/3) + 1

a = 1, b = 3/2 e f(n) = 1

nlogb a = nlog3/2 1 = n0 = 1

Logo, f(n) = 1 = !(nlogb a)

– p. 38/44


T (n) = T (2n/3) + 1

a = 1, b = 3/2 e f(n) = 1

nlogb a = nlog3/2 1 = n0 = 1

Logo, f(n) = 1 = !(nlogb a)

Pelo Caso 2, T (n) = !(log n).

– p. 38/44


T (n) = 3T (n/4) + n log n

– p. 39/44


T (n) = 3T (n/4) + n log n

a = 3, b = 4 e f(n) = n log n

– p. 39/44


T (n) = 3T (n/4) + n log n

a = 3, b = 4 e f(n) = n log n

nlogb a = nlog4 3

– p. 39/44


T (n) = 3T (n/4) + n log n

a = 3, b = 4 e f(n) = n log n

nlogb a = nlog4 3

Logo, f(n) = n log n = "(nlog4 3+!)

– p. 39/44


T (n) = 3T (n/4) + n log n

a = 3, b = 4 e f(n) = n log n

nlogb a = nlog4 3


af(n/b) = 3(n/4) log(n/4) $ (3/4)n log n

– p. 39/44


T (n) = 3T (n/4) + n log n

a = 3, b = 4 e f(n) = n log n

nlogb a = nlog4 3


af(n/b) = 3(n/4) log(n/4) $ (3/4)n log n

Pelo Caso 3, T (n) = !(n log n).

– p. 39/44


T (n) = 2T (n/2) + n log n

– p. 40/44


T (n) = 2T (n/2) + n log n

a = 2, b = 2 e f(n) = n log n

– p. 40/44


T (n) = 2T (n/2) + n log n

a = 2, b = 2 e f(n) = n log n

nlogb a = nlog2 2 = n

– p. 40/44


T (n) = 2T (n/2) + n log n

a = 2, b = 2 e f(n) = n log n


Caso 3

–p. 40/44


T (n) = 2T (n/2) + n log n

a = 2, b = 2 e f(n) = n log n


Caso 3

Mas, f(n) = n log n &= "(nlog2 2+!)

– p. 40/44


T (n) = 2T (n/2) + n log n

a = 2, b = 2 e f(n) = n log n


Caso 3

Mas, f(n) = n log n &= "(nlog2 2+!)

Portanto, o método mestre não se aplica.

– p. 40/44


T (n) = 2T (n/2) + cn

– p. 41/44


T (n) = 2T (n/2) + cn

a = 2, b = 2 e f(n) = cn

– p. 41/44


T (n) = 2T (n/2) + cn

a = 2, b = 2 e f(n) = cn


– p. 41/44


T (n) = 2T (n/2) + cn

a = 2, b = 2 e f(n) = cn


Logo, f(n) = cn = !(n) = !(nlogb a)

– p. 41/44


T (n) = 2T (n/2) + cn

a = 2, b = 2 e f(n) = cn


Logo, f(n) = cn = !(n) = !(nlogb a)

Pelo Caso 2, T (n) = !(n log n).

– p. 41/44


T (n) = 8T (n/2) + cn2

– p. 42/44


T (n) = 8T (n/2) + cn2

a = 8, b = 2 e f(n) = cn2

– p. 42/44


T (n) = 8T (n/2) + cn2

a = 8, b = 2 e f(n) = cn2


– p. 42/44


T (n) = 8T (n/2) + cn2

a = 8, b = 2 e f(n) = cn2


Logo, f(n) = cn2 = O(nlogb a!!), onde " = 1

– p. 42/44


T (n) = 8T (n/2) + cn2

a = 8, b = 2 e f(n) = cn2


Logo, f(n) = cn2 = O(nlogb a!!), onde " = 1

Pelo Caso 1, T (n) = !(n3).

– p. 42/44


T (n) = 7T (n/2) + cn2

– p. 43/44


T (n) = 7T (n/2) + cn2

a = 7, b = 2 e f(n) = cn2

– p. 43/44


T (n) = 7T (n/2) + cn2

a = 7, b = 2 e f(n) = cn2

nlogb a = nlog2 7

– p. 43/44


T (n) = 7T (n/2) + cn2

a = 7, b = 2 e f(n) = cn2

nlogb a = nlog2 7

Logo, f(n) = cn2 = O(nlogb a!!), onde " > 0

– p. 43/44


T (n) = 7T (n/2) + cn2

a = 7, b = 2 e f(n) = cn2

nlogb a = nlog2 7

Logo, f(n) = cn2 = O(nlogb a!!), onde " > 0

Pelo Caso 1, T (n) = !(nlog2 7).

– p. 43/44

Método mestre - Exercícios

1. T (n) = 2T (n/4) + 1

2. T (n) = 2T (n/4) +#n

3. T (n) = 2T (n/4) + n

4. T (n) = 2T (n/4) + n2

5. T (n) = T (n/2) + 1

6. T (n) = 4T (n/2) + n

7. T (n) = 4T (n/2) + n2

8. T (n) = 4T (n/2) + n3

– p. 44/44

Education

Análise de Algoritmos - Solução de Recorrências