2014-05-10 23:26
原题：
what is the best,worst and average case complexity for fibonacci no.s ..explain?
题目：计算斐波那契数的最好、最坏、平均复杂度是多少？
解法：计算斐波那契数倒是有好多方法，不过平均复杂度是怎么个说法？我写了三种解法：1. 白痴级的二路递归，复杂度是指数级的。2. 普通的递推算法，复杂度是线性的。3. 矩阵陈法，用快速幂可以达到对数级的时间。
代码：
1 // http://www.careercup.com/question?id=5673934611546112 2 #include3 using namespace std; 4 5 int fib1(int n) 6 { 7 if (n < 1) { 8 return 0; 9 } 10 11 if (n == 1 || n == 2) { 12 return 1; 13 } 14 15 return fib1(n - 1) + fib1(n - 2); 16 } 17 18 int fib2(int n) 19 { 20 if (n < 1) { 21 return 0; 22 } 23 24 if (n == 1 || n == 2) { 25 return 1; 26 } 27 28 int f1, f2, f3; 29 30 f1 = f2 = 1; 31 for (int i = 3; i <= n; ++i) { 32 f3 = f1 + f2; 33 f1 = f2; 34 f2 = f3; 35 } 36 return f3; 37 } 38 39 void matrixMultiply(int a[2][2], int b[2][2], int c[2][2]) 40 { 41 int i, j, k; 42 43 for (i = 0; i < 2; ++i) { 44 for (j = 0; j < 2; ++j) { 45 c[i][j] = 0; 46 for (k = 0; k < 2; ++k) { 47 c[i][j] += a[i][k] * b[k][j]; 48 } 49 } 50 } 51 } 52 53 void matrixPower(int a[2][2], int b[2][2], int n) 54 { 55 if (n < 1) { 56 b[0][0] = b[1][1] = 1; 57 b[0][1] = b[1][0] = 0; 58 return; 59 } 60 61 if (n == 1) { 62 b[0][0] = a[0][0]; 63 b[0][1] = a[0][1]; 64 b[1][0] = a[1][0]; 65 b[1][1] = a[1][1]; 66 return; 67 } 68 69 int p[2][2]; 70 matrixPower(a, p, n / 2); 71 if (n % 2) { 72 int c[2][2]; 73 matrixMultiply(p, p, c); 74 matrixMultiply(a, c, b); 75 } else { 76 matrixMultiply(p, p, b); 77 } 78 } 79 80 int fib3(int n) 81 { 82 if (n < 1) { 83 return 0; 84 } 85 86 if (n == 1 || n == 2) { 87 return 1; 88 } 89 90 int a[2][2] = { 91 { 1, 1}, 92 { 1, 0} 93 }; 94 int b[2][2]; 95 matrixPower(a, b, n - 2); 96 97 return b[0][0] + b[0][1]; 98 } 99 100 int main()101 {102 int n;103 104 while (cin >> n) {105 cout << fib3(n) << endl;106 }107 108 return 0;109 }