c++ - 为什么我的斐波那契动态规划没有给出线性时间？

Question

我正在看这个video .基本上它说使用 字典(python 的语言？)将计算从时间 O(n^2) 到 O(n) 的斐波那契。

我编写了以下代码，fibo1 应该是 O(n) 但实际上它运行起来非常慢。 fibo2 是正常的递归，它是 O(n^2) 的解决方案，但实际上它运行得比 fibo1 快得多。我怎么能理解这个？

#include <iostream>
#include <map>
int fibo1(int i, std::map<int,int>& m);
int fibo2(int i);

int main()
{
    std::map<int,int> m;
    m[1] = 1; m[2] = 1;
    int n = 40;
    std::cout << fibo1(n,m);
    //std::cout << fibo2(n);
    return 0;
}

int fibo1(int i, std::map<int,int>& m)   {
    if(m[i]==0)   {
        return fibo1(i-1,m)+fibo1(i-2,m);
    }
    return m[i];
}

int fibo2(int i) {
    if(i==1 || i==2) {
        return 1;
    }

    return fibo2(i-1)+fibo2(i-2);
}

Answer 1

您实际上从未在m[n] 处编写fib[n]，因此您永远不会查找任何内容并始终重新计算它。在 if 语句而不是返回行中使用 m[i] = fibo1(i-1,m) + fibo1(i-2,m);。