对于N-斐波那契数，这个O(log )迭代方法是如何工作的？

Question

我刚解决了需要在O(log )中找到N个斐波那契数的Codechef中的一个问题。我用了上面提到的快速倍频法这里

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 实现了一棵红黑树 (一种二进制搜索树的类型)是O(log n)。

std::map是一个排序关联容器，包含具有唯一键的键值对。键通过比较函数比较进行排序。搜索、删除和插入操作具有对数复杂度。地图通常以红黑树的形式实现.

(更不用说STL的比较功能了，根据我的经验，这是非常慢的。)

因此，实际上，您的递归算法调用另一个log n算法log n时间，使其成为O(log n * log(log n))。(说BST是O(log m)，其中m是元素的数量，log n，它变成O(log(log n)))。这本身并不是很大的差别，但是每个操作的计算成本是相对较大的。其中很大一部分归结于性能优化(或者不是优化)。此外，递归函数的计算有更多的迭代，因为它并不像迭代函数那样严格地是二进制的，尽管两者的复杂性是相同的。

关于你的第二个问题：，我不熟悉“快速加倍”算法背后的数学，所以我不能逐行解释数学是如何工作的。迭代算法的方法是只使用2次方的Fibonaccis，而不是像递归算法那样除法，从而构成最终的结果。它从LSB开始，一直往上走。