Seja
uma sequência de elementos definida do seguinte modo:
, para
. Elabore um algoritmo não recursivo para determinar o elemento
da sequência. Calcule sua complexidade em função de
.
Resposta:
;
;
para
faça:
;
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 é
.
Resposta:
para
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 é
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).