フィボナッチ数列アルゴリズムと時間複雑度分析

フィボナッチ数列アルゴリズムと時間複雑度分析
フィボナッチ数列は興味深い数列であり、応用分野は非常に広い.定義:F(n+1)=F(n)+F(n-1)興味深いことに、F(n)/F(n+1)は金分割0.618に傾く.
フィボナッチ数をどのように計算しますか?最も素朴な思想は、定義を利用する.アルゴリズム1のコードは次のとおりです.
1
2
3
4
5
6
7
8 static int Fibonacci1( int n) {      if (n == 1 || n == 2)      {          return 1;      }      return Fibonacci1(n - 1) + Fibonacci1(n - 2); }
解析のアルゴリズムの複雑さ:T(n+1)=T(n)+T(n-1)=2*T(n-1)+T(n-2)=…=F(n-1)=F(n-1)=F(n+1)は直接再帰的に呼び出すため、結果の各1は最下層のF(1)とF(2)から来るので、n番目の数を求めるためにF(n)次関数を呼び出す.フィボナッチ数列は指数成長であるため、このアルゴリズムの時間的複雑度も指数成長、すなわちO(2^n)である.
よく考えてみると、最初から後で計算しても、線形複雑度にすぎず、アルゴリズム1よりずっといいです.そこでアルゴリズム2を得る.
1
2
3
4
5
6
7
8
9
10
11 static int Fibonacci2( int n) {      int [] a = new int [n];      a[0] = 1;      a[1] = 1;      for ( int i = 2; i < n; i++)      {          a[i] = a[i - 1] + a[i - 2];      }      return a[n - 1]; }
時間の複雑さはO(n)である.
フィボナッチ数列のアルゴリズムを求めるのはもっと速いですか?答えは肯定的だ.アルゴリズム3:下図に示す結論:行列のn次方を求めればよい.2つの2次元行列の乗算回数は定数と見なすことができる.行列額nの次数は分治法を用いる、O(lg n)の複雑さだけで算出できる.したがって、このアルゴリズムの複雑度はO(lg n)であり、アルゴリズム2よりもずっと速く、特に数字が非常に大きい場合である.例えば、nが1億から4億になると、アルゴリズム2に要する時間は元の4倍になるが、アルゴリズム3は定数2だけ増加する(lg 4=2).アルゴリズムコードは次のとおりです.
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
32
33
34
35
36
37
38 static int Fibonacci3( int n) {      int [,] a = new int [2, 2] { { 1, 1 }, { 1, 0 } };      int [,] b = MatirxClub(a, n);      return b[1, 0]; }
  static int [,] MatirxClub( int [,] a, int n) {      if (n == 1) { return a; }      else if (n == 2) { return Matirx(a, a); }      else if (n % 2 == 0)      {          int [,] temp = MatirxClub(a, n / 2);          return Matirx(temp, temp);      }      else      {          int [,] temp = MatirxClub(a, n / 2);          return Matirx(Matirx(temp, temp), a);      } }
  static int [,] Matirx( int [,] a, int [,] b) {      int [,] c = new int [2, 2];      for ( int i = 0; i < 2; i++)      {          for ( int j = 0; j < 2; j++)          {              for ( int k = 0; k < 2; k++)              {                  c[i, j] += a[i, k] * b[k, j];              }          }      }      return c; }
手当たり次第にテストプログラムを書いて効率を比較した.アルゴリズム1のn=42とアルゴリズム2のn=400,000の計算に要する時間差は多くない.このことから,指数時間複雑度のアルゴリズムは恐ろしいが…アルゴリズム3はn=400,000に対してもほぼ一瞬で終わる.