Árvores de recursão podem ser empregadas para a obtenção de soluções assintoticamente justas para recorrências. Esses limites são expressos por meio da notação Theta e oferecem um poderoso recurso para a análise do desempenho de algoritmos.
Considere a recursão T(n) = T(n – a) + T(a) + cn, onde a ≥ 1 e c > 0 são constantes, e assinale a alternativa que indica uma afirmação correta a respeito de sua análise.
A árvore de recursão apresentará altura de valor igual (n/a) + 1.
O custo de todos os nós (subproblemas) a cada nível é T(a).
A recorrência pode ser classificada como homogênea.
Se T(n) ≤ cn2, então T(n) = O(n2) para qualquer valor de a e n.
Tomando T(n) ≥ cn2, T(n) = Ω(n2), se a for igual a 1.
Soluções para a tarefa
Resposta:
A árvore de recursão apresentará altura de valor igual (n/a) + 1.
Resposta:
A árvore de recursão apresentará altura de valor igual (n/a) + 1.
Explicação:
Resposta correta. Como a cada nível da árvore o tamanho dos subproblemas é reduzido de a, serão gerados (n/a) + 1 níveis até o fim da recorrência. Como a recorrência tem um termo independente T(1), ela é classificada como heterogênea. Se T(n) = cn2, teremos
T(n) = c(n – a)2 + ca + cn
= cn2 – 2can + ca + cn
= cn2 – c(2an - a – n) (para a < ½ e n > 2a)
= cn2 – cn
= cn2
= O(n2).
Se, T(n) = cn2, temos
T(n) = c(n – a)2 + ca + cn
= cn2 – 2can + ca + cn
= cn2 – c(2an - a – n) (para a < 1 e n > 2a)
= cn2 + cn
= cn2
= O(n2).