java - 使用矩阵生成斐波那契数列

Question

有一个关于Fibonacci Series的问题，我对此非常熟悉。但是有多个答案和相关的问题。当我感兴趣地挖掘它时，有一个链接到这里的解决方案

该算法通过 O(log(n)) 解决了这个问题，令人印象深刻。但我无法理解逻辑和所谓的 Matrix exponentiation [查看 wiki，但无法与之相关]。

因此，任何人都可以通过更多细节和更好的解释准确地解释他们是如何实现的[如果你可以用代码解释，更喜欢用 Java，很有帮助]。

谢谢 ：）

Answer 1

您需要了解的是算法，而不是实现。

您需要了解的第一件事是，该算法不会给您所有的斐波那契数，只有那些n是 2 的幂的数。

第二件事是，恒定大小的矩阵的乘法当然需要恒定的（ O(1) ）时间。

现在的诀窍是正确注意第 n 个斐波那契数可以通过链接中描述的矩阵的 n 次乘法形成，我将其称为M。

您现在可以通过将矩阵运算从例如 M*(M*(M*M))“重新排序”到 (M*M)*(M*M) 来获得对数复杂度。对于每个矩阵平方，您将转到M ^2n 而不是M ^n+1。