86. Fibonacci数を返す

0
1
1 = 0 + 1
2 = 1 + 1
3 = 1 + 2
5 = 2 + 3
8 = 3 + 5
13 = 5 + 8
....

[0,1,1,2,3,5,8,13 ...]

最初の二つの数字を決めて、最後の二つの数字を足して新しい数字を生成することを繰り返せば、 Fibonacci numberになる。

n番目のFibonacci数を得る関数fib(n)を実装してください。

質問

あなたの実装の時間と空間複雑性は？