Question

Saber analisar uma recorrência a partir da descrição de um dado problema, é importante para a correta avaliação da complexidade do algoritmo que será projetado. E o entendimento de como cada subproblema é expandido deve ser parte integrante dessa análise. Considere um algoritmo recursivo que, dada uma entrada de tamanho n, divide a entrada em 2 (dois) subproblemas de tamanho n/2, resolve cada um recursivamente e, por fim, combina as duas partes em um tempo O(n).



Em relação ao comportamento recursivo e ao limite assintótico desse algoritmo, analise as afirmativas a seguir (o tempo de execução do algoritmo para uma entrada de tamanho n será denotado por T(n)).



I. A árvore de recursão gerada pelo algoritmo terá tamanho log2(n).

II. Cada nível k da árvore de recursão é composto por 2k subproblemas.

III. O algoritmo tem complexidade da ordem de O(nlog2)

IV. A recursão pode ser descrita pela função T(n) = T(2n) + n.



Está correto apenas o que se afirma em:




II e III.


I, II e III.


III e IV.


II e IV.


I e II.

Answer 1

Resposta:

Está correto apenas o que se afirma em I,II e III

Answer 2

Resposta:

I, II e III

Explicação:

Seja k = {1, 2, …, K} denotar os níveis da árvore de recursão. Neste caso, k = 1 corresponde ao problema original de tamanho n, k = 2 é o primeiro nível da recursão com dois subproblemas de tamanho n/2 e, seguindo a expansão, no nível K, teremos 2k subproblemas, cada um com tamanho n/2k e, no nível K, os subproblemas terão tamanho 1. Isso quer dizer que a altura da árvore será dada por log2(n). A recursão pode ser descrita pela função T(n) = 2T(n/2) + O(n). Logo, os subproblemas serão de tamanho 1. Após K ≤ log2(n), níveis recursivos e o tempo para resolver cada subproblema de tamanho 1 será de O(1). Além disso, para um subproblema de tamanho n, há o tempo extra de combinação O(n). Então, no nível de recursão k, haverá o custo extra de 2k × O(n/2k) = O(n). Portanto, a complexidade do algoritmo será de T(n) = O(nlog(n)).