k*******t
发帖数: 144 | 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**o
发帖数: 548 | 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**o
发帖数: 548 | 3 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也行。多谢啦。
|
k*******t
发帖数: 144 | 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
|
