斐波那契数列的算法功能

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center。




已关闭8年。




我并不一定要寻找答案，但是我正在寻找这个问题要问的内容。发现这个问题正在研究面试，但不确定他们在问什么？

最佳答案

首先，您可以使用Wiki中的link更新有关斐波那契的基本数学信息。并查看this formula进行快速计算。您可以在this link中阅读有关它的所有内容。

这是用于计算第n个斐波那契数的递归函数，其时间为O(2 ^ n):

 int Fibonacci(int n) {
        if (n == 0 || n == 1)  return n;
        else
        return Fibonacci(n - 1) + Fibonacci(n - 2); }

这是计算第n个斐波那契数的更好的主意，并且时间为O(n):

int Fibonacci(int n) {
if(n <= 0) return 0;
if(n > 0 && n < 3) return 1;

int result = 0;
int preOldResult = 1;
int oldResult = 1;

for (int i=2;i<n;i++) {
    result = preOldResult + oldResult;
    preOldResult = oldResult;
    oldResult = result;
}

return result;}

这是计算第n个斐波那契数的最佳方法，时间为O(log(n)):

this link:

正如您已经怀疑的那样，这将非常相似。使用x * x矩阵的n次方

|1 0 0 0  .... 1 1|
|1
|  1
|    1
|      1
|        1
...................
...................
|          ... 1 0|

如果将此矩阵与向量相乘，这很容易理解

f(n-1), f(n-2), ... , f(n-x+1), f(n-x)

导致

f(n), f(n-1), ... , f(n-x+1)

矩阵求幂可以在O(log(n))的时间内完成(当x被认为是常数时)。

对于斐波那契递归，也有一个封闭的公式解决方案，请参见http://en.wikipedia.org/wiki/Fibonacci_number，以查找Binet或Moivre公式。

并查看:
1- nth fibonacci number in sublinear time