再来问一下word search的时间复杂度分析 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

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

相关主题
● 请教Word Search II那题的复杂度	● 一道Facebook面经难题
● 急问，Boggle (crossword)的解题思路？	● word search follow up的问题
● 找最大、第二大元素问题	● word search i/ii 复杂度多少？
● An interview question	● boggle game是不是只有backtracking的解法？
● A家onsite, OO答的真郁闷	● splunk面经，攒人品
● shortest path in matrix	● FB online puzzle请教
● F家一题	● tree vs hash
● google 电面fast phone book loopup	● 神马是剪枝，神马是回溯

相关话题的讨论汇总
话题: word话题: 复杂度话题: visit话题: 搞糊涂话题: 分析

进入JobHunting版参与讨论

1

(共1页)

l*******t 发帖数: 79	1 这个帖子（http://www.mitbbs.com/article_t/JobHunting/32524193.html）讨论的结果是O(mn4^(word))。但是如果记录了一个cell是否被visit过，visit过了就直接pass，这样复杂度没那么高吧？ http://baozitraining.org/blog/calculate-hard-runtime-complexity 感觉可以用类似这道题的思路。。。但是分析起来还是有点晕。。求高人指点！
l******s 发帖数: 3045	2 visit过的在本分支DFS后还会被backtrack回来，visit只是针对本次DFS的树枝有意义，换个分支还是non-visited
T****U 发帖数: 3344	3 应该就是这么多，后面部分取决于trie中的最长word，但是一般搜索路径都会很短，所以这个4^word 部分基本可以看作常数了【在 l******t 的大作中提到】 : 这个帖子（http://www.mitbbs.com/article_t/JobHunting/32524193.html）讨论的结果是O(mn*4^(word))。 : 但是如果记录了一个cell是否被visit过，visit过了就直接pass，这样复杂度没那么高 : 吧？ : http://baozitraining.org/blog/calculate-hard-runtime-complexity 感觉可以用类似这道题的思路。。。但是分析起来还是有点晕。。求高人指点！
l*******t 发帖数: 79	4 哦哦对的。。我搞糊涂了。。thanks~ 【在 l******s 的大作中提到】 : visit过的在本分支DFS后还会被backtrack回来，visit只是针对本次DFS的树枝有意义 : ，换个分支还是non-visited
l*******t 发帖数: 79	5 恩谢谢解答！【在 T****U 的大作中提到】 : 应该就是这么多，后面部分取决于trie中的最长word，但是一般搜索路径都会很短，所 : 以这个4^word : 部分基本可以看作常数了

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 神马是剪枝，神马是回溯	● A家onsite, OO答的真郁闷
● 攒人品，报F家面经	● shortest path in matrix
● 问道amazon的面试题	● F家一题
● 求助一个Apple有意思的面试题	● google 电面fast phone book loopup
● 请教Word Search II那题的复杂度	● 一道Facebook面经难题
● 急问，Boggle (crossword)的解题思路？	● word search follow up的问题
● 找最大、第二大元素问题	● word search i/ii 复杂度多少？
● An interview question	● boggle game是不是只有backtracking的解法？

相关话题的讨论汇总
话题: word话题: 复杂度话题: visit话题: 搞糊涂话题: 分析

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)