A lógica do fibonacci é bem simples. O número atual é resultado da soma do número anterior mais o seu anterior (n-1)+(n-2). Considerando apenas o conjunto dos números naturais, adicionamos uma regra para os números 0 e 1, cujo os seus correspondentes são eles mesmos f(0) = 0 e f(1)=1 e assim temos a sequência 0 1 1 2 3 5 ...
podemos começar com então com a que representa a função matemática de Fibonacci f(n) = f(n-1) = f(n-2), a solução recursiva.
Solução recursiva
Na solução recursiva vamos colocar:
- Nosso caso base
n = 0en = 1 - E a expressão matemática
f(n) = f(n-1) = f(n-2)
É uma solução simples e compreensiva, porém acredite não é a das melhores.
Complexity
Vamos pensar em fib(6), e realizar um teste de mesa (não vou trocar fib(1) e fib(0) por 1 e 0 no nosso teste de mesa porque não precisamos nos apegar ao valor mas ao número de instruções):
| Valor | Recursão | Total | Intruções |
|---|---|---|---|
fib(6) |
fib(5) + fib(4)
|
fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
|
13 |
fib(5) |
fib(4) + fib(3)
|
fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1)
|
8 |
fib(4) |
fib(3) + fib(2)
|
fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
|
5 |
fib(3) |
fib(2) + fib(1)
|
fib(1) + fib(0) + fib(1)
|
3 |
fib(2) |
fib(1) + fib(0)
|
2 |
Observando o resultado do nosso teste vemos algo assustador. Para exercutarmos essa função, nos a rodamos o número corresponte ao seu valor em finonacci! Ou seja pensando na perspectiva de f(x) = yda matemática, em um número n de entradas levamos exatamente y para retornar o próprio y!
Aproveitando a matemática, a f(x) = yque corresponde à complexidade de Fibonacci é $\phi$ é o Número de Ouro ($\approx 1.618$). Ou seja a complexidade de tempo dessa função é $O(1.618^n)$ mas a gente arredonda para a complexidade assinstótica de $O(2^n)$.
E quanto armazenamento? podemos ver no teste de mesa que nos igualamos as funções (f(3) = f(2)+f(1)), no fim o código recursivo acaba passando por todas as definições de f(n) e igualando ao seu valor, ou seja, para cada n valor temos salvo n definições ocupando um espaço n de memória.
Em resumo:
- Time complexity: $O(2^n)$
- Space complexity: $O(n)$
Existe um forma mais rápida de solucionar esse caso e é também simples. Muito parecida com o que nos usamos logo quando quando aprendermos fibonacci na escola.
Solução iterativa
No ensino fundamental, quando a professora pedia para calcularmos o valor de de fibonacci de 20, somávamos a sequencia de valores 20 vezes até chegar o valor correspondente, correto? Nessa solução faremos o mesmo! Vamos iterar de 2 a n somando consecutivamente até chegarmos no nosso valor.
Nesa solução iterativa vamos colocar:
- Nosso caso base
n = 0en = 1, - Uma variável
ique começa com2e incrementa atén, - Duas variáveis, uma para salvar
i-1e outrai-2no valor correspondente dei
Podemos falar que essas duas variáveis são dois ponteiros, são dois savepoints, onde eu vou deixar resgistrados valores que me importam. No fim da iteração eu apenas retorno o valor do primeiro ponteiro i-1.
Porque?
Bem durante a iteração, você vai:
- Colocar o valor de
i-1em um ponteiro temporário, pode ser umc(i-1seriaaei-2seriab), - Somar esse dois ponteiros
i-1ei-2e salvar emi-1 - Colocar o valor de
cemi-2
c morre no fim de cada ciclo da iteração, ele so serve pra fazer a troca de valores depois da soma. No fim da iteração o valor em i-1 sempre irá corresponder ao f(n) do próximo valor de i e assim que acaba temos de fato f(n).
Você pode ter olhado o código correspondente da sua linguagem e passado reto nas outras, mas se parar e olhar com calma, cada linguagem tem uma forma interessante de iterar os valores e de passar entre os ponteiros a, b e c. Na real, alguns nem tem o ponteiro c, legal né?
Uma característica que essas linguagens tem em comum é o swap, a capacidade de troca de valores entre variáveis. Vou deixar aqui uma listinha de possibilidade de swap entre linguagens.
| Linguagem | Atribuição de valores | Troca de valores |
|---|---|---|
| Java | int a = 1; int b = 0; |
a = (b += a) - a; |
| Kotlin | var (a, b) = 0 to 1 |
var (a, b) = 1 to 0 |
| Swift | var (a, b) = (0, 1) |
(a, b) = (b, a + b) |
| Dart | var (a, b) = (0, 1) |
(a, b) = (b, a + b) |
Essas sobreposições de valores causam um efeito significativo nessa versão do algoritmo de fibonacci, a solução em termos de espaço passa a ser $O(1)$, já a de tempo, $O(n)$. Porque? Bem, temos os seguintes pontos:
- Nossos ponteiros sempre serão 3 (ou 2...). Na duvida, complexidade assintótica de $O(1)$,
- Temos um fluxo de iteração de 2 para n, ou seja executamos as instruções de soma n vezes.
assim em resumo:
- Time complexity: $O(n)$
- Space complexity: $O(1)$
Bem, tudo que é bom, pode melhorar e por mais que um algoritmo $O(n)$ não seja péssimo, existe algumas soluções mais "velozes" em perpectiva de complexidade assintótica. No proximo algorítmo veremos como usar uma propriedade da algebra para resolver o problema de fibonacci, desta vez usaremos matrizes!
Top comments (0)