请教recursive backtracking问题的时间复杂度的分析 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教recursive backtracking问题的时间复杂度的分析

请教recursive backtracking问题的时间复杂度的分析# JobHunting - 待字闺中

k*t2013-09-27 07:09

1 楼

实在弄不明白，比如cc18.7: Find the longest word made of the words in a given
list，或者leetcode中的solve soduku问题，如果用recursive backtracking 时间复
杂度为何为O(2^n)啊？最好解释下，抛link也行。多谢啦。

h*o2013-09-27 07:09

2 楼

cc18.7.我怎么觉得是O（n^n）如果不考虑 DP 的话？
谁说是O(2^n）？

given

【在 k*******t 的大作中提到】

: 实在弄不明白，比如cc18.7: Find the longest word made of the words in a given
: list，或者leetcode中的solve soduku问题，如果用recursive backtracking 时间复
: 杂度为何为O(2^n)啊？最好解释下，抛link也行。多谢啦。

h*o2013-09-27 07:09

3 楼

cc18.7.我怎么觉得是O（n^n）如果不考虑 DP 的话？
谁说是O(2^n）？

given

【在 k*******t 的大作中提到】

k*t2013-09-27 07:09

4 楼

http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie 这两个题类似，link中的题更简单，只要求check一个string是否有dict的word组成的。recursion的复杂度就是O(2^n)啊。考虑DP的复杂度才是O(n*n)。虽然link里说了recursion的复杂度reduce to determine the number of possible segmentations. 可是还是想不明白

【在 h**o 的大作中提到】

: cc18.7.我怎么觉得是O（n^n）如果不考虑 DP 的话？
: 谁说是O(2^n）？
:
: given