Combinations和Subset时间复杂度比较[Leetcode]

duffywan 发表于 2015-10-17 10:14
请问是哪本书呀～！可以说一下吗

Elements of Programming Interviews

stellari 发表于 2015-2-27 23:32
那个，先自我介绍一下，我就是Leetcode上的stellari，咱还是中文聊来得方便点吧。

先澄清一点啊，我绝对 ...

谢stellari回答，对于recursion / backtracking 一类的题一直分析部清楚run time.
请教另外一题：
https://leetcode.com/discuss/643 ... ing-128ms-to-dp-0ms
这个帖子应该是你回的吧，想问下对于最基本的解法，也就是p1翻转一次往下递归，如果p2不能翻转了p1就赢了，你给的run time分析是：
T(N) = T(N-2) + T(N-3) + [T(2) + T(N-4)] + [T(3) + T(N-5)] + ...
        [T(N-5) + T(3)] + [T(N-4) + T(2)] + T(N-3) + T(N-2)
     = 2 * sum(T[i])  (i = 3..N-2)
You will find that T(N) = 2^(N-1) satisfies the above equation. Therefore, this algorithm is at least exponential.
有两个地方不懂：
1. T(n)这个式子怎么理解： 我自己分析的是
对于顶层：T(n) = (n - 1)T(n - 2)，就是如果string全是”＋“我们有n - 1个地方可以把它翻转成"--",最坏情况下对这每次翻转都要递归下去，因为已经翻转了两个，所以下一层需要处理的就是T(n-2)了。
把式子打开变成T(n) = (n - 1)(n-3)T(4) = (n - 1) (n - 3)(n-5).....1. 感觉和n!有点接近。
2. 如何reduce 到2^(N-1)

不好意思问得问题都很蠢，希望能被解答！

duffywan 发表于 2015-10-18 00:27
谢stellari回答，对于recursion / backtracking 一类的题一直分析部清楚run time.
请教另外一题：
http ...

你说的应该是对的，多谢指出。我其实是先写完S-G的算法然后再返回头来写的开头的那一段，可能是把两者混起来了。我分析的那个时间复杂度其实是：“在使用S-G函数，但是不使用DP计算函数值”的情况下的时间复杂度。

至于那个式子怎么reduce到2^(N)的，如果T(N) = 2 * sum(T(1)...T(N-2)) ，那么T(N-1) = 2 * sum(T(1)..T(N-3))。所以T(N) = T(N-1) + 2*T(N-2)。

很明显，如果T(N) = 2^N的话，那么T(N-1) = 2^(N-1), 2*T(N-2) = 2^(N-1)。后两者的和恰好是2^N。所以T(N)的表达式就是2^N。这可能听起来有点置因为果的感觉，但是一般只要能找到一个满足递推公式的通项公式，那么这个通项公式就是T(N)的表达式。在咱们遇到的题的范围内应该不会有例外。

monkerek 发表于 2015-10-17 10:46
Elements of Programming Interviews

谢谢！我最近也在看那个书，有一些variant的题目自己的思路不是很清楚 可以一起讨论下么

duffywan 发表于 2015-10-28 23:42
谢谢！我最近也在看那个书，有一些variant的题目自己的思路不是很清楚 可以一起讨论下么

可以可以~

monkerek 发表于 2015-10-29 01:26
可以可以~

给个邮箱或者联系方式呗～

stellari 发表于 2015-2-27 23:32
那个，先自我介绍一下，我就是Leetcode上的stellari，咱还是中文聊来得方便点吧。

先澄清一点啊，我绝对 ...

求问一下大神，那combination sum 1这个题 是recursion(i,end,comb,result,k-1); 不是i+1,那复杂度是应该是O(n!)对吗。但是我感觉复杂度还和sum有关系呢，比如[1,1,1] target = 10000这个case

有个疑问：subset时间复杂度就是2^n吧，结果2^n个，每次操作是1（因为是基于上一步的结果，只加了一个元素啊， 不是整个重头计算）。所以我个人认为是2^n * 1=2^n.

houhahha 发表于 2017-12-10 04:04
有个疑问：subset时间复杂度就是2^n吧，结果2^n个，每次操作是1（因为是基于上一步的结果，只加了一个元素 ...

要考虑把每一个subset的list拷贝到result的时间的话 还要再乘以一个n，就是subset里list的长度

iverson1122 发表于 2017-12-14 15:51
要考虑把每一个subset的list拷贝到result的时间的话 还要再乘以一个n，就是subset里list的长度

您好，想请教一下，是不是凡是涉及到拷贝的操作，这个操作的时间都是和拷贝内容成正比的呢？谢谢～