一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 543|回复: 3
收起左侧

[算法题] 请教一个dfs复杂度计算的问题

[复制链接] |试试Instant~ |关注本帖
osto 发表于 2015-8-8 17:34:38 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
在做dfs问题的时候经常遇到递归调用, 这个时候分析复杂度我不是在在行.
请教各位有总结出什么规律可以参考吗?

举个例子
  1. int dfs(vector<int>& A, int start ,int end) {
  2.     if (start == end) {
  3.         return 1;
  4.     }
  5.     int maxValue = INT_MIN;
  6.     for (int i = start; i < end; ++i) {
  7.         int result1 = dfs(A, i, i);
  8.         int result2 = dfs(A, i+1, end);
  9.         maxValue = max(min(result1, result2), maxValue);
  10.     }
  11.     return maxValue;
  12. }
复制代码
还有这种带cache的
  1. int dfsCache(vector<int>& A, int start ,int end, map<string, int>& cache) {
  2.     if (start == end) {
  3.         return 1;
  4.     }
  5.     string key = to_string(start) + "-" + to_string(end);
  6.     if (cache.find(key) != cache.end()) {
  7.         return cache.at(key);
  8.     }
  9.     int maxValue = INT_MIN;
  10.     for (int i = start; i < end; ++i) {
  11.         int result1 = dfsCache(A, i, i, cache);
  12.         int result2 = dfsCache(A, i+1, end, cache);
  13.         maxValue = max(min(result1, result2), maxValue);
  14.     }
  15.     cache[key] = maxValue;
  16.     return maxValue;
  17. }
复制代码
这两种复杂度分别是多少?
有没有什么普适的方法?


我自己尝试分析了下, 列出算式大概是
T(n) = n + T(n-1) + T(n-2) + T(n-3) + ... + T(1)
然后就凌乱了, 求指点.


另外, 如果函数是这样的情况呢?
  1. int dfs(vector<int>& A, int start ,int end) {
  2.     if (start == end) {
  3.         return 1;
  4.     }
  5.     int maxValue = INT_MIN;
  6.     for (int i = start; i < end; ++i) {
  7.         int result1 = dfs(A, start, i);
  8.         int result2 = dfs(A, i+1, end);
  9.         maxValue = max(min(result1, result2), maxValue);
  10.     }
  11.     return maxValue;
  12. }
复制代码
stellari 发表于 2015-8-8 21:42:29 | 显示全部楼层
osto 发表于 2015-8-8 20:03
> 如果这种情况不好直接看出来,你就多往下写两步找规律:
> = n +  (n-1) + 2*[T(n-2) + ... T(1)]
> ...
它内部还有个循环, 所以我觉得是O(n^2)

你说的是对的,抱歉我之前没把代码看清楚。

理由是:第一层递归中有
f(n) = f(n-1) + f(n-2) + ... + f(1)
当f(n-1)返回时,f(n-2) ... f(1)都已经算出来了,所以f(n)的实际执行时间是
T(n) = T(n-1) + (n-2) * C
同理T(n-1) = T(n-2) + (n-3) * C
所以
T(n) = C* [n-2 + n-3 + n-4 + ... 1] ~ O(n^2)

----------------------------
因为T(n)和T(n/b)不同级别, 正如你所说的分摊不了


这要看a和b究竟是常数还是n的函数。我的理解是,如果a是常数,那么T(n) = aT(n/b) + n 这种情况分摊不了,因为n(线性)级别大于a(常数),例如mergesort。如果a=Const * n,那么就可以分摊。T(n) = aT(n-1) + 1能忽略1是因为无论a是什么,1(常数)级别都不会超过a,所以总是可以省掉。

如果某递归函数的运行时间可写成下述形式:
T(n) = sum(T(recursive_calls)) + g(n)

那么只要g(n)小于等于“本函数调用自身的次数”的级别,那么这个g(n)就可以去掉(即‘分摊’)。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-8-8 19:08:29 | 显示全部楼层
T(n) = n + T(n-1) + T(n-2) ... + T(1)
如果这种情况不好直接看出来,你就多往下写两步找规律:
= n +  (n-1) + 2*[T(n-2) + ... T(1)]
= n + (n-1) + 2*[n-2 + 2*[T(n-3) + ... T(1)]]
= n + (n-1) + 2(n-1) + 4[T(n-3)+...T(1)]
....
这下基本就看出来了
= n + (n-1) + 2(n-2) + 4(n-3) + 8(n-4) + ... +2^(n-1)*(1)

这样还是不能直接得到一个明确表达式怎么办?写出它的下一项:
T(n+1) = n+1 + n + 2(n-1) + 4(n-2) + 8(n-3) + ...+ 2^(n-1)*2 + 2^n*1

两者相减得:
T(n+1) - T(n)  = (n+1-n) + [n-(n-1)] + 2[(n-1)-(n-2)] + 4[(n-2)-(n-3)] + ... + 2^(n-1)*(2-1) + 2^n
= 1 + 1 + 2 + 4 + ... 2^(n-1) + 2^n = 2^(n+1)

如果要让T(n)能够满足这个条件,那么T(n)必等于2^(n+1)。因此时间复杂度是O(2^n)

其实从复杂度分析的角度来说,你不需要写出T(n)= n + T(n-1) +...这个式子中的第一项n,因为这是个线性时间项,相当于在T(n-1), T(n-2), …… T(1)这n-1次函数中各分摊了一个常数时间,这是可以忽略不计的(但是,mergesort中的线性时间项则不能忽略不计。因为它只有2次递归函数调用。这个线性时间并不能以常数形式分摊到这2次调用中)

用了memoization的话,就可以降低到线性时间了。因为每次调用时的end其实都一样,所以cache的结果必然是xxxx-end这种形式,只有前半部分不同。因此总共有O(n)种情况。而这段程序实质上把每个xxx-end的情况都(仅仅)算了一遍,所以最后的总时间是O(n)。当然,比起iterative形式的DP来说,n前面的常系数会略高。

---

你不妨用类似的思路自己试着推推最后一种情况
回复 支持 1 反对 0

使用道具 举报

 楼主| osto 发表于 2015-8-8 20:03:45 | 显示全部楼层
stellari 发表于 2015-8-8 19:08
T(n) = n + T(n-1) + T(n-2) ... + T(1)
如果这种情况不好直接看出来,你就多往下写两步找规律:
= n +  ...

> 如果这种情况不好直接看出来,你就多往下写两步找规律:
> = n +  (n-1) + 2*[T(n-2) + ... T(1)]
> = n + (n-1) + 2*[n-2 + 2*[T(n-3) + ... T(1)]]
> = n + (n-1) + 2(n-1) + 4[T(n-3)+...T(1)]

这里n + (n-1) + 2(n-1) + 4[T(n-3)+...T(1)] 应该为n + (n-1) + 2(n-2) + 4[T(n-3)+...T(1)] 吧

非常感谢提供推导思路.


关于n项, 能不能认为在 T(n) = aT(n/b) + n 这种形式是必须考虑, 因为T(n)和T(n/b)不同级别, 正如你所说的分摊不了,  同理类似T(n) = aT(n-1) + 1 这种1也可以忽略, 而T(n) = aT(n-1) + n 这种n就不能忽略,这样理解对吗?
不过砸T(n) = aT(n-1)这种形式也是需要预先知道它复杂度是n^2才知道可以忽略呢.
我现在经验不够不能一眼辨别出来, 还是写上去比较妥当.

>用了memoization的话,就可以降低到线性时间了。因为每次调用时的end其实都一样,所以cache的结果必然是xxxx-end这种形式,只有前半部分不同。因此总共有O(n)种情况。而这段程序实质上把每个xxx-end的情况都(仅仅)算了一遍,所以最后的总时间是O(n)。当然,比起iterative形式的DP来说,n前面的常系数会略高。

这个我觉得应该不只O(n)的, 你想想单纯 f(A, start, end) = f(A, start+1, end)这种就已经是O(n)了, 它内部还有个循环, 所以我觉得是O(n^2), 因为它的iterative DP是两层循环, 如果直接就这样分析不知道怎么下手..带memoization觉得绕了许多,只能死记它和iterative形式的DP的复杂度等价,  但刷题的时候发现有时候memoization还是会Time limited, 非得用迭代才能AC.







回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 18:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表