アルゴリズムと計算量

フィボナッチ数の計算と計算量


フィボナッチ数


フィボナッチ数の計算: 定義通り


演習 14.3

  1. クラス Fib1 で fib[0], fib[1], fib[2], fib[10], fib[20], fib[30], fib[40] を計算しなさい.
  2. 上記の計算をすると,数が大きくなると極端に計算時間がかかるようになるが,その原因を考えなさい.

フィボナッチ数の計算: 積み上げ式


演習 14.4

  1. クラス Fib2 のプログラムを読んで,このアルゴリズムがフィボナッチ数の計算になっていることを確認しなさい.
    何故 tmp という一時変数が必要なのかを考えなさい.
  2. クラス Fib2 で fib[0], fib[1], fib[2], fib[10], fib[20], fib[40], fib[60], fib[90] を計算しなさい.
  3. fib[45] を Fib1 と Fib2 で計算し,計算の速さを比較しなさい.
  4. Fib2 が Fib1 に較べて計算が速い理由を考えなさい.

アルゴリズム


計算量とは


計算量の計算例


フィボナッチ数の計算の計算量

アルゴリズム (時間) 計算量
定義通り O( ((1 + sqrt(5)) / 2)n-1 )
積み上げ式 O( n )
行列計算 O( log n )

ここで log は底が 2 の対数 log2 のことである.


演習 14.5

  1. 積み上げ式のフィボナッチ数の計算について計算量を求めなさい.
  2. さらに高速なフィボナッチ数の求め方があるので調べてみなさい.
    [ヒント] 行列を使って計算する.

次の資料へ 授業計画のページへ
2012年6月10日作成
伊知地 宏
Copyright (C) Hiroshi Ichiji, 2012. All rights reserved.