Considere a seguinte função
:
função f(n)
se n>1 entao:
imprima(estudando)
f(n/2)
f(n/2)
Assumindo que
seja uma potência de 2 , quantas palavras estudando são impressas? Escreva uma relação de recorrência da função
e resolva-a.
Resposta:
A recorrência é
. Pelo Teorema Mestre, temos que são impressas
linhas.
função f(n)
se n>1 entao:
imprima(estudando)
f(n/2)
f(n/2)
Assumindo que
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
e a condição de contorno é
já que para
não imprimimos nada.
Passo 3
Para resolver pelo Teorema Mestre, note que aqui
,
e
. Como
e
com
, estamos no caso 1 do Teorema Mestre, o que dá
Passo 4
Para obter a solução exata, considere a árvore de recursão: no nível
(contando do 0) há
chamadas que imprimem 1 vez, e o número total de níveis de impressão vai de
até
. Logo o total é
Resposta
A recorrência é
com
, e a solução exata é
, ou seja
.