Considere o código-fonte que segue:int f1(int n) { if (n...
Considere o código-fonte que segue:
int f1(int n) {
if (n == 0 II n == 1) return n;
else return (2 * f1(n-1) + 3 * f1(n-2)); }
int f2(int n) {
int a; int[] X = new int [n];
int[] X = new int [n]; int[] Z = new int [n];
X [0] = Y [0] = Z [0] = 0;
X [1] = 1; Y [1] = 2; Z [1] = 3;
for (a = 2; a <= n; a ++) {
X [a] = Y [a-1] + Z [a-2];
Y [a] = 2 * X [a]; Z [a] = 3 * X [a]; }
return X [n]; }
Qual é o tempo de execução de f1(n) e f2(n),
respectivamente?
F1 temos fibonacci recursivo, que tem complexidade O(2n).
F2 temos fibonacci não recursivo, que tem complexidade O(n).
Esse é um assunto que não tenho domínio, então se alguém tiver algo a acrescentar ou mesmo retificar, eu agradeceria.
Força Guerreiro!!!!!!
Nem ferrando que fibonacci recursivo é 2n...
Deveria ser 2^n
@Leandro Henrique concordo contigo. Imagino que seja 2 elevado a N, porém, na hora de pega a questão perderam esse detalhe.
Pensei o mesmo que o Leandro, acabei fazendo por eliminação. Pode ter sido na transcrição da questão
o(n^2) e o(n)
Alternativa correta: C - O(2n) e O(n)
Vamos entender por que essa é a alternativa correta e analisar as alternativas incorretas.
Função f1(n)
A função f1(int n)
é uma função recursiva que define uma relação de recorrência. A análise do tempo de execução de uma função recursiva depende de quantas vezes a função é chamada recursivamente.
O código da função é o seguinte:
int f1(int n) {
if (n == 0 || n == 1) return n;
else return (2 * f1(n-1) + 3 * f1(n-2)); }
A função f1
chama a si mesma duas vezes para calcular f1(n-1)
e f1(n-2)
. Isso implica que a profundidade da recursão cresce exponencialmente com n
. Portanto, a complexidade de tempo para f1(n)
é O(2n), pois o número de chamadas recursivas cresce exponencialmente.
Função f2(n)
A função f2(int n)
utiliza laços para calcular seu resultado em vez de recursão. O código relevante é:
int f2(int n) {
int a; int[] X = new int [n];
int[] X = new int [n]; int[] Z = new int [n];
X [0] = Y [0] = Z [0] = 0;
X [1] = 1; Y [1] = 2; Z [1] = 3;
for (a = 2; a <= n; a++) {
X [a] = Y [a-1] + Z [a-2];
Y [a] = 2 * X [a]; Z [a] = 3 * X [a]; }
return X [n]; }
O laço for
executa n-1
iterações (de 2 até n
). Dentro do laço, as operações executadas têm complexidade constante O(1)
. Portanto, a complexidade do tempo de execução para f2(n)
é O(n), pois o laço domina a complexidade e executa linearmente em relação a n
.
Análise das Alternativas
A - O(2n) e O(2n): Incorreta. A função f2(n)
tem complexidade O(n)
, não O(2n)
.
B - O(n) e O(2n): Incorreta. A função f1(n)
tem complexidade O(2n)
, não O(n)
.
D - O(n) e O(n): Incorreta. A função f1(n)
tem complexidade O(2n)
, não O(n)
.
E - O(n) e O(log n): Incorreta. A função f1(n)
tem complexidade O(2n)
, e a função f2(n)
tem complexidade O(n)
, não O(log n)
.
Portanto, a alternativa C - O(2n) e O(n) é a resposta correta, pois reflete corretamente a complexidade de tempo das funções f1(n)
e f2(n)
.