2014-05-10 23:26
原题：
what is the best,worst and average case complexity for fibonacci no.s ..explain?
题目：计算斐波那契数的最好、最坏、平均复杂度是多少？
解法：计算斐波那契数倒是有好多方法，不过平均复杂度是怎么个说法？我写了三种解法：1. 白痴级的二路递归，复杂度是指数级的。2. 普通的递推算法，复杂度是线性的。3. 矩阵陈法，用快速幂可以达到对数级的时间。
代码：
// http://www.careercup.com/question?id=5673934611546112
#include <iostream>
using namespace std; int fib1(int n)
{
if (n < ) {
return ;
} if (n == || n == ) {
return ;
} return fib1(n - ) + fib1(n - );
} int fib2(int n)
{
if (n < ) {
return ;
} if (n == || n == ) {
return ;
} int f1, f2, f3; f1 = f2 = ;
for (int i = ; i <= n; ++i) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
} void matrixMultiply(int a[][], int b[][], int c[][])
{
int i, j, k; for (i = ; i < ; ++i) {
for (j = ; j < ; ++j) {
c[i][j] = ;
for (k = ; k < ; ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
} void matrixPower(int a[][], int b[][], int n)
{
if (n < ) {
b[][] = b[][] = ;
b[][] = b[][] = ;
return;
} if (n == ) {
b[][] = a[][];
b[][] = a[][];
b[][] = a[][];
b[][] = a[][];
return;
} int p[][];
matrixPower(a, p, n / );
if (n % ) {
int c[][];
matrixMultiply(p, p, c);
matrixMultiply(a, c, b);
} else {
matrixMultiply(p, p, b);
}
} int fib3(int n)
{
if (n < ) {
return ;
} if (n == || n == ) {
return ;
} int a[][] = {
{, },
{, }
};
int b[][];
matrixPower(a, b, n - ); return b[][] + b[][];
} int main()
{
int n; while (cin >> n) {
cout << fib3(n) << endl;
} return ;
}