递归算法时间复杂度和空间复杂度分析 类型一(快速排序 & 归并排序) 快速排序 时间复杂度分析：注意：p = partition(a, l, r)这里的时间复杂度为O(n)最好情况：每次都是二分，T(n) = 2*T(n/2) + O(n) = O(nlogn)最坏情况：每次划分出一个数值，T(n) = T(n-1) + T(1) + O(n) = O(n^2)一般情况：不平衡分割，T(n) = T(n/10) + T(9n/10) + O(n) = O(nlogn) 空间复杂度分析(考虑递归深度)：最好情况：每次都是二分，O(logn)最坏情况：每次划分出一个数值，O(n)归并排序 时间复杂度分析：归并排序每次都是二分，T(n) = 2*T(n/2) + O(n) = O(nlogn) 空间复杂度分析(考虑递归深度)：递归深度是log(n) merge(a, l, m, r)需要额外的空间，但是它是临时使用的空间复杂度是O(logn + n)总结 由于快速排序没有数组的拷贝，所以空间复杂度低，同时在一般情况中的事件复杂度也是有良好的表现，所以快速排序应用的更为广泛 类型二(二分查找 & 二叉树中序遍历) 二分查找 时间复杂度分析：每次都是二分，T(n) = T(n/2) + O(1) = O(logn) 空间复杂度分析(考虑递归深度)：O(logn)二叉树中序遍历 假设是完美二叉树 时间复杂度分析：最好的情况下：每次输入规模减半，T(n) = 2*T(n/2) + O(1) = O(n)最差的情况下：二叉树只有左子树(相当于逐个遍历)，T(n) = T(n-1) + T(1) + O(1) = O(n) 空间复杂度分析(考虑递归深度)：最好的情况下：O(logn)最差的情况下： O(n)对比总结类型一和类型二的区别是中间有没有O(n)的操作递归函数的每一步都很重要，如果多做了一点，很可能最后的结果和线性没有区别 类型三(组合 & 排列) combination 时间复杂度分析：每个数字有两种情况，取或者不取，T(n) = O(2^n) 空间复杂度分析(考虑递归深度)：O(n)permutation 时间复杂度分析：T(n) = n*T(n-1) = O(n!) 空间复杂度分析(考虑递归深度)：O(n) 记忆递归 fibonacci_origin 时间复杂度分析：T(n) = T(n-1)+T(n-2)+O(1)2T(n-2)<T(n)<2T(n-1)T(n) = O(2^n)实际上是O(1.168^n)黄金比例 空间复杂度分析(考虑递归深度)：O(n)fibonacci_memorization 时间复杂度分析：O(n) 空间复杂度分析(考虑递归深度)：记忆深度和递归深度都是O(n) //TODO leetcode741 & leetcode312 参考文献 花花酱 LeetCode Time/Space Complexity of Recursive Algorithms – 刷题找工作 SP4_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/86909.html
