注解

回溯问题

Posted by Futari on 2022-07-04

Estimated Reading Time 2 Minutes

Words 670 In Total

Viewed Times

回溯问题

回溯问题可以理解为树搜索问题，之所以回溯可以剪枝就是基于树的概念，不断的深度遍历到叶子端，然后返回上一节点进行递归（回溯）

对于回溯的时间复杂度的分析，可能从树的角度不好分析，那么就先找到应该有多少种结果的情况，每一种情况的消耗复杂度（这里均指O的量级复杂度）是多少，最后相乘空间复杂度如果没有额外的空间开辟，那么就是树的深度> ## 比如：子集问题 ##### 其时间复杂度是O(n*2的n次方)，为什么？数据规模是n，即求n个数的子集理解为树，不要从回溯的方式上去想，递归的深度是n，如n=3时，递归深度也为3（从第0层开始） ![回溯](https://img-blog.csdnimg.cn/20190724155127277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3J1dGFvMDkyMw==,size_16,color_FFFFFF,t_70) 每一层的操作数据规模（数据规模方面不好想，明显底层的被操作的次数是最多的） ###### 每一个元素的状态不是取就是不取，所以产生一共![[公式]](https://www.zhihu.com/equation?tex=2%5En) 种状态

而且每一种状态都需要On的时间复杂度去构造（因为是n个元素的排列，实际中可能是小于这个复杂度或者是大于，但是在数量级上还是O（n）的）

排列问题分析：

时间复杂度：： $O(n\times n!)$ 。因为一共 $n!$ 种排列，每种排列都需要 $O(n)$ 的构造时间，最终时间复杂度为 $O(n\times n!)$ 。

空间复杂度： $O(n)$ ，递归深度为n，所以系统栈所用空间为 $O(n)$ 。

组合问题分析：

时间复杂度： $O(C_n^k \times k)$ ，总共有 $C_n^k$ 种组合，每种组合需要 $O(k)$ 的时间复杂度。另一方面，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度 $O(n\times 2^n)$ 。

空间复杂度： $O(n)$ ，递归深度为n，所以系统栈所用空间为 $O(n)$ 。

N皇后问题分析

时间复杂度： $O(N!)$ ，其中 N 是皇后数量，由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 N 列可以选择，第二个皇后最多有 N-1列可以选择…。

空间复杂度： $O(N)$ ，递归深度为n，所以系统栈所用空间为 $O(N)$ 。

解数独问题分析

时间复杂度： $O(9^m)$ ，m是’.’的数目。

空间复杂度： $O(n^2)$ ，n是数独盘子的大小，递归的深度是 $n^2$ 。

如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。也欢迎您共享此博客，以便更多人可以参与。如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。谢谢！