如何将此递归函数转换为迭代函数？
#include <cmath>
int M(int H,int T){
if (H == 0) return T;
if (H + 1 >= T) return pow(2,T) - 1;
return M(H - 1,T - 1) + M(H,T - 1) + 1;
}
解决方法
这个函数速度慢的主要原因是因为它具有指数复杂性,并且它一次又一次地重新计算相同的成员.一种可能的治疗方法是记忆模式(用C
here中的例子轻松解释).我们的想法是将每个结果存储在具有快速访问权限的结构中(例如,数组),并且每次需要它时,检索已经预先计算的结果.当然,这种方法受到你的记忆大小的限制,所以它不适用于极大的数字……
在你的情况下,我们可以做类似的事情(保持递归但记住结果)：
#include <cmath>
#include <map>
#include <utility>
std::map<std::pair<int,int>,int> MM;
int M(int H,int T){
std::pair<int,int> key = std::make_pair(H,T);
std::map<std::pair<int,int>::iterator found = MM.find(key);
if (found!=MM.end()) return found->second; // skip the calculations if we can
int result = 0;
if (H == 0) result = T;
else if (H + 1 >= T) result = pow(2,T) - 1;
else result = M(H - 1,T - 1) + 1;
MM[key] = result;
return result;
}
关于时间复杂度,C映射是树映射,因此在那里搜索N * log(N)的顺序,其中N是映射的大小(已经计算的结果的数量).还有C的哈希映射,它们是STL的一部分,但不是标准库的一部分,因为已经是mentioned on SO.哈希映射承诺不断搜索时间(虽然没有指定常量的值:)),所以你也可能试一试.
