c++ - 如何在 log(n) 时间内或更好地计算该序列的第 n 个元素？

Question

1 4 10 22 45 88 167

这个序列是斐波那契数与其自身的卷积。复发是

a[n] = a[n-1] + a[n-2] + Fibonacci[n+2]

如果您假设斐波那契数列从0,1,1,2,3,5 ...( http://oeis.org/A213587 )

我怎样才能生成它是对数时间或更快？请注意，这不是作业，也不是任何比赛问题。我正在研究斐波那契应用序列。

Answer 1

这是一个封闭的公式，因此几乎可以保证O(1)（使用 Mathematica 计算）

输入：

RSolve[{a[n] == a[n - 2] + a[n - 1] + Fibonacci[n + 2], a[1] == 1, a[2] == 4}, a[n], n]

输出（点击这里查看完整尺寸）：

您将不得不使用一些浮点运算，但您仍然可以从双精度数据类型中获得更高的精度。如果精度是个问题，请使用 GMP 或其他任意精度库。

Answer 2

我能够通过将递归关系转换为斐波那契卷积在 log n 时间内解决这个问题。最后，递归关系只包含卢卡斯数和斐波那契数。所以我能够在 2*log n 中解决它。我一旦我弄清楚如何在这里写数学符号，就会在这里写下整个证明。

Answer 3

这不是问题的实际答案，只是一种生成整个序列的方法O(n)

如果您的意思是O(log(n))仅计算第 n 个元素的时间复杂度，并非全部取决于n它实际上很容易。如果您遍历，您可以轻松地O(1)为每个元素进行适当的记忆。

我会假设这个：

a[1] = 1, a[2] = 1, fib[1] = 0, fib[2] = 1, fib[3] = 1

然后只是迭代和记忆，a[n-1]以及a[n-2]一路上：fib[n-1]fib[n-2]

long an_1 = 1;  // a[2]
long an_2 = 1;  // a[1]
long fib_1 = 2; // fib[4]
long fib_2 = 1; // fib[3]

// Starts with a[3]
while (true)
{
    long fib = fib_1 + fib_2;
    long an = an_1 + an_2 + fib;

    std::cout << an;

    fib_2 = fib_1;
    fib_1 = fib;
    an_2 = an_1;
    an_1 = an;
}

编辑：这称为摊销复杂性。计算到n第 - 个元素需要O(n)一些步骤，但是当你到达这一点时，所有元素1都n可用，计算每个元素的成本是O(1). 正式的证明更详细一些，但这就是想法。