Combination Sum 这道题的时间和空间复杂度是多少？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Combination Sum 这道题的时间和空间复杂度是多少？

Combination Sum 这道题的时间和空间复杂度是多少？# JobHunting - 待字闺中

P*e2018-07-05 07:07

1 楼

这个解法：
http://www.cnblogs.com/grandyang/p/4419259.html
时间空间复杂度怎么去分析？ (n^k)? n是什么，k是什么？
面试时候时间复杂度需要算到多精确? 大概说个轮廓？还是会要给出精确的公式？对这
类recusion+backtracking 的复杂度分析有什么好办法吗？

n*g2018-07-05 07:07

2 楼

这一道题基本上就是在看你每个元素是否应该选进去, 当然不是perm, 而是一个comb.
但整体运算速度大概就是每个元素是否该被选进去的时间.
先说一个类似的题, 78. 如果是一个简简单单的subset 的话, 那你的时间就是 2 ^ n,
每个元素都会被选进去0 或者 1次.
那再看这个题. 你每个元素都会被考虑, 假设每个元素都能被选k次的话, 那就是 k ^
n. 至于你写的 n ^ k, 不知道哪里来的.
空间的话应该是stack space, 也就是你最多call几次这个函数.
最多call几次呢? 是你target-nums[i]的最多次数.. 大概就是k次吧.. 所以空间是k

P*e2018-07-05 07:07

3 楼

不对吧。空间复杂度是k*n^k.
参考这里 https://github.com/awaemmanuel/LeetCode-Kamyu/blob/master/Python/
combination-sum.py

: 这一道题基本上就是在看你每个元素是否应该选进去, 当然不是perm, 而是一个
comb.

: 但整体运算速度大概就是每个元素是否该被选进去的时间.

: 先说一个类似的题, 78. 如果是一个简简单单的subset 的话, 那你的时间就是
2 ^ n,

: 每个元素都会被选进去0 或者 1次.

: 那再看这个题. 你每个元素都会被考虑, 假设每个元素都能被选k次的话, 那就
是 k ^

: n. 至于你写的 n ^ k, 不知道哪里来的.

: 空间的话应该是stack space, 也就是你最多call几次这个函数.

: 最多call几次呢? 是你target-nums[i]的最多次数.. 大概就是k次吧.. 所以空
间是k

【在 n*********g 的大作中提到】

: 这一道题基本上就是在看你每个元素是否应该选进去, 当然不是perm, 而是一个comb.
: 但整体运算速度大概就是每个元素是否该被选进去的时间.
: 先说一个类似的题, 78. 如果是一个简简单单的subset 的话, 那你的时间就是 2 ^ n,
: 每个元素都会被选进去0 或者 1次.
: 那再看这个题. 你每个元素都会被考虑, 假设每个元素都能被选k次的话, 那就是 k ^
: n. 至于你写的 n ^ k, 不知道哪里来的.
: 空间的话应该是stack space, 也就是你最多call几次这个函数.
: 最多call几次呢? 是你target-nums[i]的最多次数.. 大概就是k次吧.. 所以空间是k