Fibonacci数列

メモ化再帰とかの話読んでたらちょっと思い出したので書く。

let fib = n => n === 0 ? 0 : (n === 1 ? 1 : (n > 1 ? fib(n - 1) + fib(n - 2) : void(0)));

みたいなのを書くと、 {\displaystyle \mathcal{O} ({\alpha}^n)} ( {\displaystyle \alpha = \frac{\sqrt{5} + 1}{2}}) の計算量になるはず(ほんまか?)

これを { \displaystyle \mathcal{O} (n)}まで下げたい

まあ、こうする

let fib_seq = (n) => {
  if(n === 0) return [0];
  if(n === 1) return [1, 0];
  if(n > 1) {
    let seq = fib_seq(n - 1);
    return [seq[0] + seq[1], ...seq];
  }
};

let fib = n => fib_seq(n)[0];

fib_seqn番目までの数列を取得するやつなんですけど、やってることってn - 1番目までの配列をとってきてその添字01を足して配列に積むだけなので、たぶん {\displaystyle \mathcal{O} (n)}で済むはず。その一番上を拾うといい感じになる。

このやり方は去年大学の講義でPrologで実装するやつを見たんだけど、忘れそうだったから一応書いておいた。

まあ普通に漸化式解いて一般項求めて誤差を丸めれば  {\displaystyle \mathcal{O} (1) }だが…*1

*1:調べたら行列とか使って頑張ると  {\displaystyle \mathcal{O} (n \log n)}まで下がるらしい