SóProvas


ID
4182682
Banca
IFPI
Órgão
IF-PI
Ano
2016
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

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? 

Alternativas
Comentários
  • 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