问如何在log(n)时间或更短的时间内计算此序列的第n个元素？

EN

我能够在log时间内解决这个问题，通过将递归关系转换为斐波那契数，递归关系只包含卢卡数和斐波那契数，我可以在2*log .I中解决它，一旦我知道如何在这里写数学符号，我会在这里写下整个证明。

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

输入

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

Output (单击here查看完整大小)：

​

​

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

这不是问题的实际答案，只是在 O(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;
}

编辑：这称为amortized complexity。计算到n-th元素需要O(n)个步骤，但是当您达到这一步时，从1到n的所有元素都可用，因此计算每个元素的成本是O(1)。正式的证明要详细一点，但这就是我们的想法。