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]

输出(点击here查看全尺寸):

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