Considere a seguinte função f(n) :
função f(n)
se n>1 entao:
imprima(estudando)
f(n/2)
f(n/2)
Assumindo que n seja uma potência de 2 , quantas palavras estudando são impressas? Escreva uma relação de recorrência da função f(n) e resolva-a.

Resposta:

A recorrência é T(n)=2 T(n / 2)+1. Pelo Teorema Mestre, temos que são impressas O(n) linhas.

Passo 1

A função f(n) recebe um n que é potência de 2 e, se n>1, imprime a palavra “estudando” uma vez e faz duas chamadas recursivas com f(n/2). O conteúdo envolve análise de recorrências usando Teorema Mestre ou árvore de recursão.

Passo 2

Definimos T(n) como o número de vezes que “estudando” é impresso. Como em cada chamada com n>1 imprimimos 1 vez e depois fazemos duas subchamadas com tamanho n/2, a relação de recorrência fica
T(n)=2,Tl(tfrac n2r)+1
e a condição de contorno é T(1)=0 já que para n=1 não imprimimos nada.

Passo 3

Para resolver pelo Teorema Mestre, note que aqui a=2, b=2 e f(n)=1=Theta(n^0). Como n^logba=n^log2 2=n^1 e f(n)=O(n^1-varepsilon) com varepsilon=1, estamos no caso 1 do Teorema Mestre, o que dá
T(n)=Thetal(n^logbar)=Theta(n)

Passo 4

Para obter a solução exata, considere a árvore de recursão: no nível i (contando do 0) há 2^i chamadas que imprimem 1 vez, e o número total de níveis de impressão vai de i=0 até log2n-1. Logo o total é
sumi=0^log2n-12^i=2^log2n-1=n-1

Resposta

A recorrência é T(n)=2T(n/2)+1 com T(1)=0, e a solução exata é T(n)=n-1, ou seja Theta(n).

Exercícios relacionados