为什么我对斐波纳契的动态编程没有给出线性时间？

Question

我正在看这个视频.基本上它说使用dictionary(python的语言？)将计算从时间O(n ^ 2)到O(n)的fibonacci.

我编程了以下代码,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

你从来没有真正写过fib[n]at m[n],所以你永远不会查找任何东西并且总是重新计算它.使用m[i] = fibo1(i-1,m) + fibo1(i-2,m);if语句,而不是回线.