关于word search的复杂度，和暴力解法的疑问
来源：8-6 二维平面上的回溯法 Word Search
软件工程小白菜
2019-07-28
波波老师您好，关于这道题，我还有两个地方不太理解。
在老师给出的答案中，时间复杂度为O(m*n*m*n)，空间复杂度为O(m*n)。我对这两个复杂度的理解不知道是否正确，希望老师指正。以下是我所做出的尝试：
对于时间复杂度而言，首先我们要对m*n的每一个格子都进行搜索（对应代码中的两个for循环），这是第一个m*n。然后对于每一个格子来说，我们最坏的情况是把除了这个格子外的所有格子搜索一遍，每一次搜索对应一次递归调用占用的时间，这对应了后一个m*n。
对于空间复杂度而言，显而易见我们使用了m*n的二维数组，但我想问递归调用不会占用空间复杂度吗？
除了老师给出的回溯解法，我还在思考这道题是否有暴力解法，以及暴力解法的时间，空间复杂度，但我想了很久，感觉回溯法就是这道题的暴力解法，请问老师是否正确，还是说有别的暴力解法？我实在想不出还有什么所谓的“暴力方法”能解决这道题，我也尝试对这道题使用迭代法进行解决，参考了老师之前运用stack把递归转化成迭代的技术，但这样迭代后，感觉时间复杂度和空间复杂度应该和递归解法一致？
1回答
-
1
时间复杂度，你的分析完全正确：）
空间复杂度，是的，递归会使用空间。但是二维数组使用的空间和递归使用的空间没有嵌套关系。我们没有在递归的过程中不断地开空间，所以，使用的是二维数组的空进 m * n 加上递归的空间 m * n ，即O(2 * m * n) = O(m * n)
2
是的！回溯法就是暴力解法！暴力法的本质是遍历所有可能。但是怎么遍历所有可能？对于很多问题来说，需要使用回溯法！：）
3
对的，递归转非递归不会带来复杂度的变化，除了个别问题空间复杂度会变低以外（没有了递归栈深度），算法本身不可能通过递归转非递归，产生时间复杂度的差距。因为两个写法本质逻辑是等价的，只不过是使用系统栈，还是自己调用栈操作的区别而已：）
继续加油！：）
312019-07-29
相似问题