Fibonacci矩阵算法的运行时间

Question

我试着向达斯古普塔、帕帕迪米特里欧和瓦兹拉尼学习算法。我发现了一个我无法回答的问题，任何帮助/暗示都将不胜感激。

找到Fibonacci级数的方法之一是使用: Fn Fn+1=0 1 1 1^n。F0 F1

按照我的说法，运行时间应该是O(n^2 * Log n)。"n^2"用于n位数的乘法，对于乘法次数需要"log“。

然而，这本书表明运行时间将是O(M(n)) where M(n)=theta(n^a), 1<=a<=2。你能告诉我哪里出了问题吗？

Answer 1

计算斐波那契数的两种可能方法：

1)在expression中，有一个封闭形式的表达式，通过将它作为线性递归来导出。

2)这似乎是可对角化的矩阵，因此您可以将它写成PDP^-1，其中D是对角的，(PDP^-1)^n=P D^n P^-1。因为D是对角线的，所以你可以用每个对角线元素的幂来计算它的幂。事实上，fibonacci矩阵是在application中明确提到的。