Seja f1, f2, ldots, fn uma sequência de elementos definida do seguinte modo: f1=0, f2=1, f3=1, fj=fj-1-fj-2+fj-3, para j>3. Elabore um algoritmo não recursivo para determinar o elemento fn da sequência. Calcule sua complexidade em função de n.
Resposta:
f[1]:=0;
f[2]:=1 ;
f[3]:=1;
para j=4 ldots n faça: f[j]:=f[j-1]-f[j-2]+f[j-3];
Note que os elementos são preenchidos percorrendo o vetor uma única vez. Cada elemento é obtido com complexidade constante, pela consulta e soma dos três elementos anteriores. Sendo assim, a complexidade do algoritmo acima é O(n).

Passo 1

O enunciado define uma sequência \ f_1, f_2, …, f_n \ pelas condições iniciais \ f_1=0, f_2=1, f_3=1 \ e pela relação de recorrência \ f_j = f_{j-1} - f_{j-2} + f_{j-3} \ para j>3. O conteúdo envolve programação dinâmica/iterativa para evitar recursão e análise de complexidade.

Passo 2

Inicializamos um vetor f de tamanho n e atribuímos as condições iniciais: \ f[1] := 0 \ f[2] := 1 \ f[3] := 1

Passo 3

Para j variando de 4 até n, usamos a fórmula dada para preencher f[j] de forma iterativa, ou seja, em cada iteração fazemos: \ f[j] := f[j-1] - f[j-2] + f[j-3]

Passo 4

Como percorremos o vetor apenas uma vez, de j=4 até n, e cada iteração faz um número constante de operações (três acessos e duas subtrações e uma soma), a complexidade do algoritmo é linear no tamanho de n.

Resposta

O algoritmo não recursivo que inicializa f[1]=0, f[2]=1, f[3]=1 e itera de j=4 até n com f[j] = f[j-1] - f[j-2] + f[j-3] tem complexidade O(n).

Exercícios relacionados