注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
在做dfs问题的时候经常遇到递归调用, 这个时候分析复杂度我不是在在行.
请教各位有总结出什么规律可以参考吗?
举个例子- int dfs(vector<int>& A, int start ,int end) {
- if (start == end) {
- return 1;
- }
- int maxValue = INT_MIN;
- for (int i = start; i < end; ++i) {
- int result1 = dfs(A, i, i);
- int result2 = dfs(A, i+1, end);
- maxValue = max(min(result1, result2), maxValue);
- }
- return maxValue;
- }
复制代码 还有这种带cache的- int dfsCache(vector<int>& A, int start ,int end, map<string, int>& cache) {
- if (start == end) {
- return 1;
- }
- string key = to_string(start) + "-" + to_string(end);
- if (cache.find(key) != cache.end()) {
- return cache.at(key);
- }
- int maxValue = INT_MIN;
- for (int i = start; i < end; ++i) {
- int result1 = dfsCache(A, i, i, cache);
- int result2 = dfsCache(A, i+1, end, cache);
- maxValue = max(min(result1, result2), maxValue);
- }
- cache[key] = maxValue;
- return maxValue;
- }
复制代码 这两种复杂度分别是多少?
有没有什么普适的方法?
我自己尝试分析了下, 列出算式大概是
T(n) = n + T(n-1) + T(n-2) + T(n-3) + ... + T(1)
然后就凌乱了, 求指点.
另外, 如果函数是这样的情况呢?- int dfs(vector<int>& A, int start ,int end) {
- if (start == end) {
- return 1;
- }
- int maxValue = INT_MIN;
- for (int i = start; i < end; ++i) {
- int result1 = dfs(A, start, i);
- int result2 = dfs(A, i+1, end);
- maxValue = max(min(result1, result2), maxValue);
- }
- return maxValue;
- }
复制代码 |