c++ - 为什么记忆的解决方案比正常的递归解决方案慢?
问题描述
我正在实现一个函数来计算第 n 个加泰罗尼亚语数。序列的公式如下:
我注意到记忆的解决方案比正常的递归解决方案慢。这是我的代码:
#include <bits/stdc++.h>
using namespace std;
int catalan_number_recursive(int n){
if (n == 0) return 1;
else{
int ans = 0;
for (int i = 0; i < n; i++){
ans += catalan_number_recursive(i)*catalan_number_recursive(n - 1 - i);
}
return ans;
}
}
int catalan_number_memo(int n, map<int, int> memo){
memo[0] = memo[1] = 1;
if (memo.count(n) != 0){
return memo[n];
}
else{
int ans = 0;
for (int i = 0; i < n; i++){
ans += catalan_number_memo(i, memo)*catalan_number_memo(n - 1 - i, memo);
}
memo[n] = ans;
return memo[n];
}
}
int main(){
printf("Catalan Numbers - DP\n\n");
int num = 12;
auto start1 = chrono::high_resolution_clock::now();
printf("%dth catalan number (recursive) is %d.\n", num, catalan_number_recursive(num));
auto finish1 = chrono::high_resolution_clock::now();
chrono::duration<double> elapsed1 = finish1 - start1;
cout << "Time taken: " << elapsed1.count() << "s.\n\n";
auto start2 = chrono::high_resolution_clock::now();
printf("%dth catalan number (memo) is %d.\n", num, catalan_number_memo(num, {}));
auto finish2 = chrono::high_resolution_clock::now();
chrono::duration<double> elapsed2 = finish2 - start2;
cout << "Time taken: " << elapsed2.count() << "s.\n";
return 0;
}
n = 12 的代码输出为:
Catalan Numbers - DP
12th catalan number (recursive) is 208012.
Time taken: 0.006998s.
12th catalan number (memo) is 208012.
Time taken: 0.213007s.
此外,当我尝试使用 n = 20 时,它给了我一个负值,这是不正确的,但对于较小的值,它是正确的。谢谢您的回答。
解决方案
#include <bits/stdc++.h>
using namespace std;
int catalan_number_recursive(int n){
if (n == 0) return 1;
else{
int ans = 0;
for (int i = 0; i < n; i++){
ans += catalan_number_recursive(i)*catalan_number_recursive(n - 1 - i);
}
return ans;
}
}
int catalan_number_memo(int n, map<int, int>& memo){
memo[0] = memo[1] = 1;
if (memo.count(n) != 0){
return memo[n];
}
else{
int ans = 0;
for (int i = 0; i < n; i++){
ans += catalan_number_memo(i, memo)*catalan_number_memo(n - 1 - i, memo);
}
memo[n] = ans;
return memo[n];
}
}
int main(){
printf("Catalan Numbers - DP\n\n");
int num = 12;
auto start1 = chrono::high_resolution_clock::now();
printf("%dth catalan number (recursive) is %d.\n", num, catalan_number_recursive(num));
auto finish1 = chrono::high_resolution_clock::now();
chrono::duration<double> elapsed1 = finish1 - start1;
cout << "Time taken: " << elapsed1.count() << "s.\n\n";
auto start2 = chrono::high_resolution_clock::now();
map<int, int> m;
printf("%dth catalan number (memo) is %d.\n", num, catalan_number_memo(num, m));
chrono::duration<double> elapsed2 = finish2 - start2;
cout << "Time taken: " << elapsed2.count() << "s.\n";
return 0;
}
这是您的代码,但有一个更改 - 地图(现在是 map<int, int>&)通过可变引用而不是值传递。
发生的事情是,以前程序正在复制地图并将复制的地图作为递归参数传递,所以
0:你并没有真正记住任何东西。在每个返回点,学习值只被放入该函数唯一的映射中,因此没有跨调用学习。它仍然是指数级的。
1:非常慢。在每次递归时,您都会复制整个数据结构,而原始代码只有一个循环和。
现在我修复了它,程序运行如下:
Catalan Numbers - DP
12th catalan number (recursive) is 208012.
Time taken: 0.00236639s.
12th catalan number (memo) is 208012.
Time taken: 0.000103588s.
推荐阅读
- python - Python简化包含OR和AND的if条件
- sql-server - 在 WHERE 子句中添加条件会产生更多结果
- symfony - 实体在更改后不更新
- hibernate - 使用通用生成器时出错
- java - WebDriverWait 在 Selenium 4 中已弃用
- javascript - 如何将每个循环变量值推入数组
- javascript - JSON。JAVA 和 PHP 检查表单值是否存在
- solr - SOLR - 从给定搜索请求的相交多边形中获取所有文档条目
- java - 不是一个文件中的 JSON 对象异常,但不同的 json 文件有效
- postgresql - Symfony 4 + Api 平台无法自动验证类型为“NULL”的值。在 nativeSQL 查询上