algorithm - 这种用于第 N 个斐波那契数的 O(log n) 迭代方法如何工作？

Question

我刚刚解决了a problem in Codechef这需要在 O(log n) 中找到第 N 个斐波那契数。我使用了提到的快速加倍方法 here :

F(2N)   = F(N) * ( 2F(N+1) - F(N) )
F(2N+1) = F(N+1)^2 + F(N)^2

下面是我的代码示例。迭代版本在上面给出的链接中的代码示例中给出:

快速加倍递归

#include <map>
#include <iostream>
using namespace std;

#define long long long
const long M = 1000000007; // modulo
map<long, long> m;

long F(long n)
 {
    if(m.count(n))return m[n];

    long a, b;
    if((n&1) == 0)
    {
        a = F(n/2)%M;
        b = F((n/2) + 1)%M;
         return m[n] = (((2*a*b) % M - (a*a)%M) + M) % M;
     }
    else
    {
        a = F((n+1)/2)%M;
        b = F((n-1)/2)%M;
        return m[n] = ((a*a) % M + (b*b)% M) % M;
    }
 }

int main()
{
    m[0] = 0;
    m[1] = m[2] = 1;
    printf("%lld", F(100000000));
}

快速加倍迭代

#include <iostream>
using namespace std;

#define long long long
const long MOD = 1000000007;

long F(long n)
{
    long a = 0, b = 1, d, e, c;
    int i = 31;
    while(i >= 0)
    {
        d = (a * (((b * 2 - a) + MOD) % MOD)) % MOD;
        e = ((a * a) % MOD + (b * b) % MOD) % MOD;
        a = d;
        b = e;
        if(((n >> i) & 1) != 0)
        {
            c = (a + b) % MOD;
            a = b;
            b = c;
        }
        i--;
    }

    return a;
}

int main()
{
    printf("%lld", F(1000000000));
} 

使用前者的解决方案得到了一个 TLE，而后者是一个 AC。

现在，我的问题是:

• 除了“递归开销”之外，是否还有其他因素使递归解决方案变慢 - 例如 std::map 的使用？
• 迭代方法究竟是如何工作的？虽然这两种方法都使用快速倍增公式，但我不清楚迭代版本的执行情况。

有人可以给我解释一下迭代版本的执行吗？

Answer 1

对于您的第一个问题:主要问题是您对std::map 的使用。插入和查找，因为 std::map implements a red-black tree (一种二叉搜索树)，是 O(log n)。

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

(更不用说与 STL 的比较功能，根据我的经验，速度非常慢。)

因此，实际上，您的递归算法正在调用另一个 log n 算法 log n 次，使其成为 O(log n * log(log n)) 。 (说BST是O(log m) 其中m是元素个数，log n，就变成了O(log (log n)).) 这本身区别不大，但是每次操作的计算量比较大。其中大部分归结为性能优化(或非优化)。此外，递归函数的计算迭代次数更多，因为它不像迭代函数那样严格是二元的，即使两者具有相同的复杂度。

关于您的第二个问题:我不熟悉“快速加倍”算法背后的数学原理，因此无法逐行解释数学原理。看起来，迭代算法的方法是仅使用 2 的幂斐波那契来组合最终结果，而不是像递归算法那样进行除法。它从 LSB 开始，一直向上。