面试题：C++ 递归函数性能优化之记忆化技术

记忆化原理

记忆化（Memoization）是一种优化技术，用于提高递归算法的性能。它通过保存递归函数已经计算过的结果，避免对相同输入重复计算，从而减少计算量。当递归函数再次遇到相同的输入时，直接从记忆化的数据结构（通常是哈希表或数组）中获取结果，而无需重新计算。

C++ 中实现记忆化

以背包问题为例，假设递归函数定义如下：

// 未优化的递归函数
int knapsack(int capacity, int weights[], int values[], int n) {
    if (n == 0 || capacity == 0) {
        return 0;
    }
    if (weights[n - 1] > capacity) {
        return knapsack(capacity, weights, values, n - 1);
    } else {
        return std::max(
            values[n - 1] + knapsack(capacity - weights[n - 1], weights, values, n - 1),
            knapsack(capacity, weights, values, n - 1)
        );
    }
}

使用记忆化优化：

#include <iostream>
#include <unordered_map>

// 记忆化数据结构
std::unordered_map<std::pair<int, int>, int> memo;

// 优化后的递归函数
int knapsack(int capacity, int weights[], int values[], int n) {
    if (n == 0 || capacity == 0) {
        return 0;
    }
    std::pair<int, int> key(capacity, n);
    if (memo.find(key) != memo.end()) {
        return memo[key];
    }
    if (weights[n - 1] > capacity) {
        memo[key] = knapsack(capacity, weights, values, n - 1);
    } else {
        memo[key] = std::max(
            values[n - 1] + knapsack(capacity - weights[n - 1], weights, values, n - 1),
            knapsack(capacity, weights, values, n - 1)
        );
    }
    return memo[key];
}

时间复杂度分析

优化前：对于背包问题，未优化的递归算法时间复杂度为 $O(2^n)$。因为在每一步递归调用中，都有两种选择（放入物品或不放入物品），随着递归深度增加，调用次数呈指数级增长。
优化后：使用记忆化后，由于每个子问题只计算一次，时间复杂度降为 $O(n \times capacity)$。这里 $n$ 是物品数量，$capacity$ 是背包容量。这是因为记忆化哈希表最多存储 $n \times capacity$ 个不同的子问题结果。

空间复杂度分析

优化前：空间复杂度主要由递归调用栈决定，最坏情况下为 $O(n)$，其中 $n$ 是递归的深度。
优化后：除了递归调用栈的空间 $O(n)$，还需要额外的空间存储记忆化结果，即哈希表。哈希表最多存储 $n \times capacity$ 个元素，所以总的空间复杂度为 $O(n \times capacity)$。

星途面试题库

面试题：C++ 递归函数性能优化之记忆化技术

知识考点

面试题答案

记忆化原理

C++ 中实现记忆化

时间复杂度分析

空间复杂度分析