Fibonacci (Programação Dinâmica) em Zig — Implementação e Explicação
A sequência de Fibonacci é uma das sequências mais famosas da matemática: cada número é a soma dos dois anteriores. A abordagem ingênua recursiva tem complexidade exponencial O(2^n), mas com programação dinâmica podemos reduzi-la para O(n).
Como Funciona
A sequência começa com F(0) = 0, F(1) = 1, e para n >= 2: F(n) = F(n-1) + F(n-2).
Abordagens
- Top-Down (Memoização): recursão com cache dos resultados já calculados
- Bottom-Up (Tabulação): preenche uma tabela iterativamente de baixo para cima
- Espaço Otimizado: mantém apenas os dois últimos valores
Visualização
Recursão ingênua para F(5) — muitas chamadas repetidas:
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
/ \ / \ / \
F(2) F(1) F(1) F(0) F(1) F(0)
/ \
F(1) F(0)
Com programação dinâmica (tabulação):
i: 0 1 2 3 4 5
F[i]: 0 1 1 2 3 5
↑ ↑
| |
F[2]=F[1]+F[0] F[4]=F[3]+F[2]
Espaço otimizado — apenas dois valores:
prev=0, curr=1
→ prev=1, curr=0+1=1 (F(2)=1)
→ prev=1, curr=1+1=2 (F(3)=2)
→ prev=2, curr=1+2=3 (F(4)=3)
→ prev=3, curr=2+3=5 (F(5)=5)
Implementação em Zig
const std = @import("std");
const Allocator = std.mem.Allocator;
/// Fibonacci ingênuo — O(2^n) — apenas para comparação
pub fn fibRecursivo(n: u64) u64 {
if (n <= 1) return n;
return fibRecursivo(n - 1) + fibRecursivo(n - 2);
}
/// Fibonacci com memoização (top-down) — O(n) tempo, O(n) espaço
pub fn fibMemoizado(n: u64, allocator: Allocator) !u64 {
if (n <= 1) return n;
const tamanho: usize = @intCast(n + 1);
const memo = try allocator.alloc(?u64, tamanho);
defer allocator.free(memo);
@memset(memo, null);
memo[0] = 0;
memo[1] = 1;
return fibMemoHelper(n, memo);
}
fn fibMemoHelper(n: u64, memo: []?u64) u64 {
const idx: usize = @intCast(n);
if (memo[idx]) |valor| return valor;
const resultado = fibMemoHelper(n - 1, memo) + fibMemoHelper(n - 2, memo);
memo[idx] = resultado;
return resultado;
}
/// Fibonacci com tabulação (bottom-up) — O(n) tempo, O(n) espaço
pub fn fibTabulacao(n: u64, allocator: Allocator) !u64 {
if (n <= 1) return n;
const tamanho: usize = @intCast(n + 1);
const tabela = try allocator.alloc(u64, tamanho);
defer allocator.free(tabela);
tabela[0] = 0;
tabela[1] = 1;
var i: usize = 2;
while (i <= n) : (i += 1) {
tabela[i] = tabela[i - 1] + tabela[i - 2];
}
return tabela[@intCast(n)];
}
/// Fibonacci com espaço otimizado — O(n) tempo, O(1) espaço
pub fn fibOtimizado(n: u64) u64 {
if (n <= 1) return n;
var prev: u64 = 0;
var curr: u64 = 1;
var i: u64 = 2;
while (i <= n) : (i += 1) {
const proximo = prev + curr;
prev = curr;
curr = proximo;
}
return curr;
}
pub fn main() !void {
const stdout = std.io.getStdOut().writer();
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
try stdout.print("Sequência de Fibonacci (primeiros 20 termos):\n", .{});
for (0..20) |i| {
try stdout.print("F({d}) = {d}\n", .{ i, fibOtimizado(@intCast(i)) });
}
// Comparação de métodos
const n: u64 = 40;
try stdout.print("\nF({d}) com tabulação: {d}\n", .{ n, try fibTabulacao(n, allocator) });
try stdout.print("F({d}) com memoização: {d}\n", .{ n, try fibMemoizado(n, allocator) });
try stdout.print("F({d}) otimizado: {d}\n", .{ n, fibOtimizado(n) });
}
Análise de Complexidade
| Método | Tempo | Espaço |
|---|---|---|
| Recursivo ingênuo | O(2^n) | O(n) pilha |
| Memoização (top-down) | O(n) | O(n) |
| Tabulação (bottom-up) | O(n) | O(n) |
| Espaço otimizado | O(n) | O(1) |
| Exponenciação de matriz | O(log n) | O(1) |
Quando Usar Cada Abordagem
- Memoização: quando nem todos os subproblemas precisam ser resolvidos
- Tabulação: quando a ordem dos subproblemas é clara e todos são necessários
- Espaço otimizado: quando só precisa do resultado final, não de toda a sequência
- Matriz: quando n é extremamente grande (veja Fibonacci por Matriz)
Recursos Relacionados
- Fibonacci por Exponenciação de Matriz — Fibonacci em O(log n)
- Exponenciação Rápida — Base para Fibonacci matricial
- Knapsack (Mochila) — Outro problema clássico de DP
- LCS — Subsequência Comum — DP com duas sequências