二叉树时间复杂度与空间复杂度_二叉树时间复杂度与空间复杂度的关系

2024年 5月 26日上午10:02 • 激活谷笔记

递归算法时间复杂度和空间复杂度分析
　　类型一(快速排序 & 归并排序)

　　快速排序

　　时间复杂度分析：注意：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

二叉树时间复杂度与空间复杂度_二叉树时间复杂度与空间复杂度的关系

相关推荐