Questão 4182682

• Banca: IFPI
• Órgão: IF-PI
• Ano: 2016
• Provas: IFPI - 2016 - IF-PI - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

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? 

• A. O(2n) e O(2n).
• B. O(n) e O(2n).
• C. O(2n) e O(n).
• D. O(n) e O(n).
• E. O(n) e O(log n).

Gabarito: C

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