再来问一下word search的时间复杂度分析 - 未名空间MITBBS历史存档

再来问一下word search的时间复杂度分析

再来问一下word search的时间复杂度分析# JobHunting - 待字闺中

l*t2015-09-01 07:09

1 楼

这个帖子（http://www.mitbbs.com/article_t/JobHunting/32524193.html）讨论的结果是O(m*n*4^(word))。
但是如果记录了一个cell是否被visit过，visit过了就直接pass，这样复杂度没那么高
吧？
http://baozitraining.org/blog/calculate-hard-runtime-complexity 感觉可以用类似这道题的思路。。。但是分析起来还是有点晕。。求高人指点！

l*s2015-09-01 07:09

2 楼

visit过的在本分支DFS后还会被backtrack回来，visit只是针对本次DFS的树枝有意义
，换个分支还是non-visited

T*U2015-09-01 07:09

3 楼

应该就是这么多，后面部分取决于trie中的最长word，但是一般搜索路径都会很短，所
以这个4^word
部分基本可以看作常数了

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

: 这个帖子（http://www.mitbbs.com/article_t/JobHunting/32524193.html）讨论的结果是O(m*n*4^(word))。
: 但是如果记录了一个cell是否被visit过，visit过了就直接pass，这样复杂度没那么高
: 吧？
: http://baozitraining.org/blog/calculate-hard-runtime-complexity 感觉可以用类似这道题的思路。。。但是分析起来还是有点晕。。求高人指点！

l*t2015-09-01 07:09

4 楼

哦哦对的。。我搞糊涂了。。thanks~

【在 l******s 的大作中提到】

: visit过的在本分支DFS后还会被backtrack回来，visit只是针对本次DFS的树枝有意义
: ，换个分支还是non-visited

l*t2015-09-01 07:09

5 楼

恩谢谢解答！

【在 T****U 的大作中提到】

: 应该就是这么多，后面部分取决于trie中的最长word，但是一般搜索路径都会很短，所
: 以这个4^word
: 部分基本可以看作常数了