杭州市网站建设公司,如何把网站上传到空间,没有网站可以做seo,自己如何建设网站聊天室上一篇文章使用递推方程的方法求解了插入排序和二分归并的时间复杂度#xff0c;本文来求解快速排序的时间复杂度#xff0c;同样是利用了递推方程法#xff0c;但是求解该递推方程的方法与以前不一样#xff1a;差消法 文章目录1. 快速排序的时间复杂度求解2. 总结1. 快速… 上一篇文章使用递推方程的方法求解了插入排序和二分归并的时间复杂度本文来求解快速排序的时间复杂度同样是利用了递推方程法但是求解该递推方程的方法与以前不一样差消法 文章目录1. 快速排序的时间复杂度求解2. 总结1. 快速排序的时间复杂度求解 这里求解的是快速排序的平均时间复杂度并非求解的是最坏情况时间复杂度为什么 想想上一篇文章都是可以很容易的列出求解时间复杂度的递推式子。而在求解快速排序的平均情况时间复杂度时有一些不太一样。
假设A[p,…,r] 的元素都不相等以首元素A[1]对数组划分使得
小于x的元素被放在A[p,…,q-1]大于x的元素被放在A[q1,…,r]
然后递归的对A[p,…,q-1]和A[q1,…,r]进行快速排序的过程。
那么上述的工作量就是子问题工作量划分问题的工作量
上述过程的输入情况如下
有n种可能的输入
对上面的每种输入划分的比较次数都是n-1
那么由此可以计算出工作量总和 那么假设首元素排好序在每个位置的概率都是相等的则可求出快速排序的平均工作量总工作量/元素个数 可以看出上述的递推方程式是关于全部历史的递推方程很难通过迭代法进行求解。
对于高阶的地拖方程一般使用差消法进行求解。利用两个方程相减将右边的项尽可能消去以达到降阶的目的。 差消化简 迭代求解 可以看出最终求解的快速排序的平均情况下的时间复杂度是nlognnlognnlogn级别的。这一结果正是我们所熟悉的结果。
2. 总结
对于高阶递推方程的求解要先用差消发进行化简为一阶递推方程然后再使用迭代法进行计算。
