递归算法时间复杂度和空间复杂度分析
类型一(快速排序 & 归并排序)
快速排序
时间复杂度分析：注意：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/94577.html
