メモ。フィボナッチ数の算出の効率化

単純にフィボナッチ数を求める方法で思いつくのは再帰処理なんだけど、ちょっと大きい数字だと処理に時間がかかる。O(N^2)らしいです。
そこで、過去に算出したものはMapに突っ込むというメモ化をすれば早くなる(O(N))けど、これも番号が大きいとMapを圧縮してNGとなる。

いろいろ調べたところ、行列を使って求める方法を使うとO(logN)になるみたい。
以下のように記述。



ロジックの解釈がまだよく分かっていないところもありますが。有名なテクニックらしい。おぼえなきゃ。

javaのlong型の制限により、大きい数字は求められませんがBigDecimalに変えたりしたらどうなるのでしょうね??
関連記事


--------------------------------------------------------------------------------------

コメントの投稿

非公開コメント

このブログについて
  • 全記事一覧(時間順)
  • このブログについて
  • 私のプロフィール
  • 当ブログで扱っている動画について
  • 記事違いなコメントのお返事

  • カテゴリー
    twitter
    カレンダー
    09 | 2017/10 | 11
    1 2 3 4 5 6 7
    8 9 10 11 12 13 14
    15 16 17 18 19 20 21
    22 23 24 25 26 27 28
    29 30 31 - - - -
    Amazon
    でたらめな当ブログにぴったりな商品を自動で表示するみたいです。



    月別アーカイブ
    プロフィール

    たづみ

    Author:たづみ
    ・1981年生まれの男
    ・もう少し詳細なプロフィールはこちらで

    最新コメント
    アクセスランキング
    [ジャンルランキング]
    日記
    1120位
    アクセスランキングを見る>>

    [サブジャンルランキング]
    会社員・OL
    239位
    アクセスランキングを見る>>