带Memoization的斐波那契程序运行更慢，求性能差异原因

你遇到的问题核心是缓存完全没生效，还额外增加了不必要的开销，具体原因和解决方法如下：

问题根源 #

你的代码里，map<int, int> mp = {}是fibNum函数的局部变量——每次递归调用fibNum，都会新建一个空的map。这意味着：

• 之前递归计算出的斐波那契值根本不会被缓存下来，所有子问题还是会重复计算，和无缓存版本的递归逻辑完全一致。
• 每次调用还要承担map的构造、析构，以及find操作的额外性能开销，这直接导致运行时间比无缓存版本还长。

修正方案 #

要让缓存真正生效，必须让所有递归调用共享同一个缓存容器，最简单的方式是把map改成静态变量：

#include <iostream>
#include <map>

using namespace std;

int fibNum(int n) {
    static map<int, int> mp; // 静态变量，整个程序生命周期内只初始化一次
    if(mp.find(n) != mp.end()){
        return mp[n];
    }
    if (n == 1 || n == 2){
        return 1;
    } else if (n == 0){
        return 0;
    } else {
        int answer = fibNum(n - 1) + fibNum(n - 2);
        mp[n] = answer; 
        return answer;
    }
    return 0;
}

int main() {
    int term; cin >> term;
    
    time_t start,end;
    time(&start);
    ios_base::sync_with_stdio(false); 

    cout << fibNum(term) << endl;

    time(&end);

    double timeTaken = double(end - start);
    cout << "Time taken by program is : " << fixed 
        << timeTaken << ' ' << " sec\n"; 

    return 0;
}

另外，因为斐波那契的参数n是连续的整数，用vector代替map会更高效——vector的随机访问是O(1)时间，比map的O(logn)查找速度更快，能进一步提升性能。

内容的提问来源于stack exchange，提问作者kohtzerui