运行斐波那契矩阵算法的时间

Question

我正在尝试向 Dasgupta、Papadimittriou 和 Vazirani 学习算法。我发现了一个我无法回答的问题，任何 help/hints 将不胜感激。

查找斐波那契数列的方法之一是使用： [Fn Fn+1]=[0 1 1 1]^n 。 [F0 F1]

这个运行的时间按照我的说法，应该是O(n^2 * Log n)。 "n^2"表示n位数的乘法，"log n"表示需要乘法的次数。

但是，该书建议 运行 时间为 O(M(n))，其中 M(n)=theta(n^a), 1<=a<=2。你能告诉我哪里错了吗？

Answer 1

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

1) 在 https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

处有一个封闭形式的表达式，您可以将其视为线性递归来导出

2) 这似乎是可对角化的矩阵，因此您可以将其写为 PDP^-1，其中 D 是对角线且 (PDP^-1)^n=P D^n P^-1。由于 D 是对角线，您可以通过取每个对角线元素的幂来计算它的幂。事实上，斐波那契矩阵在 https://en.wikipedia.org/wiki/Diagonalizable_matrix#An_application

中明确提及

Answer 2

让我们更详细地了解算法。

你说得对，然后算法执行 O(log n) 次乘法，但为了分析 运行 时间，我们需要查看实际相乘的数字有多大。斐波那契数列呈指数增长。事实上，它们逐渐增长为 Θ(φⁿ)。一个数的位数与该数的以 2 为底的对数成正比，因此第 n 个斐波那契数的二进制表示的位数大致为 lg φⁿ = n lg φ = Θ(n).

我们可以按照您的方式进行分析，因为我们正在进行 O(log n) 次乘法运算，并且每次乘法运算最多使用 n 位数字，并且每次乘法运算都需要时间 O( n²) 时间 运行 时间将是 O(n² log n)，但这不是一个紧密的界限.

为了把事情收紧，让我们考虑一下如何写这个算法的运行时间的递推关系。如果我们想将矩阵提高到 n 次方，我们递归地将矩阵提高到 (n/2) 次方，然后对结果进行平方（如果 n 是奇数，则可能乘以原始矩阵的另一个副本）。假设将两个 (n/2) 位数相乘的成本是 O(n²)，这给了我们递归性

T(n) = T(n/2) + O(n²).

使用主定理，我们看到这解决了 O(n²) 而没有对数项。直觉上，这样做的原因是最后一个乘法比之前的任何乘法做的工作多得多，事实上，将所有前面的乘法的工作相加得出的结果渐近地由最后一个乘法支配。这样就摆脱了日志因素。

这里的另一个见解是我们实际上可以比 O(n²) 更快地乘以 n-digit 个数。多年来开发了许多算法（著名的是 Karatsuba 的算法，以及最近的 Furer 的算法）运行 时间 O(n^α) 对于一些常数 1 ≤ α < 2。如果我们使用其中一种更快的算法，则递归变为

T(n) = T(n/2) + O(n^α)

根据主定理，这解决了 O(n^α)，与您的来源相匹配。

总结：

1. 我们首先确认我们相乘的数字在第n步有Θ(n)位。

2. 然后我们使用朴素的乘法算法编写了 运行 时间的递推关系，该算法求解为没有任何对数因子的二次项。

3. 最后，我们通过使用更好的乘法算法来收紧我们的 运行 时间限制，改进了递推关系。