1

我使用了迭代方法和递归方法，但在这两种情况下，我都没有更快地得到 fibo(10^6) 的结果，即。复杂度为 O(logN)。

迭代方法：

static BigInteger fibo(long n){
    BigInteger a=new BigInteger("1");
    BigInteger b=new BigInteger("2");
    BigInteger c=new BigInteger("0");
    for(long i=3;i<=n;i++){
        c=a.add(b);
        a=b;
        b=c;
    }
    return c;
}
4

2 回答 2

1

仅计算nth 值的封闭形式：

封闭式斐波那契公式

您可以在Wolfram MathWorld和Wikipedia上阅读有关该主题（包括此公式）的更多信息。

不幸的是，你不能BigInteger在这里使用，但我认为你应该可以用 a 来做到这一点BigDecimal（虽然我还没有测试过）。

于 2013-02-05T10:29:15.507 回答
0

如果您想找出大 n 的fib(n)的值，您需要使用矩阵求幂法，即用于求解线性递推方程的方法。

矩阵求幂的最大优势在于其运行时间只需 O(k^3 * logN)，其中 N 是我们正在计算的矩阵的幂，k 是矩阵的大小。

检查下面提到的计算大 n 的斐波那契的 python 代码片段（具有 10^9+7 的模型，使数字在 int 范围内）。您可以在此博客中找到相同的详细说明。

matrix_mult函数将作为参数给出的两个矩阵相乘并返回它们的乘积。

def matrix_mult(A, B):
    C = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                C[i][k] = (C[i][k] + (A[i][j]*B[j [k])%mod)%mod
return C

fast_expo函数计算并返回 (matrix^power)，这是负责 O(logn) 运行时间的函数。

def fast_expo(matrix, power):
    if(power==1):
        return matrix
    else:
        if(power%2==0):
            matrix1 = fast_expo(matrix, power/2)
            return matrix_mult(matrix1, matrix1)
        else:
            return matrix_mult(matrix, fast_expo(matrix, power-1))

使用预先计算的矩阵作为参数之一调用该函数。在斐波那契的情况下，矩阵是 [[1, 1], [1, 0]]。

matrix = [[1, 1], [1, 0]]
matrix_n = fast_exponentiation(matrix, number-2)
print (matrix_n[0][0] + matrix_n[0][1]) % 1000000007

对于所有 n>2，这里的幂应该是 M^(n-2)，其中 M 是基本矩阵，因为您已经有了 f(n) 的前 2 个值，即 f(1) 和 f(2)。

于 2015-01-17T07:43:34.717 回答