最容易理解最全的快排的最好时间复杂度分析
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high){
pivot=Partition(L,low,high);//返回枢轴,操作次数为n
QSort(L,low,pivot-1);//对枢轴左边进行排序
QSort(L,pivot+1,high);//对数轴右边进行排序
}
}
最好的情况下,枢轴对两边的划分都很均匀,用递归树来表示如下图:
方法一:
根据代码我们知道,每一层的递归操作次数为该次递归所传入的元素个数,忽略每次减去的枢轴(1个元素并没有给到下一层,但是每层这里减掉一个常数对复杂度的分析影响不大,所以暂时忽略),即:
第1层是n次,
第2层有2次递归,每次n/2次,共n次操作,
第3层有4次递归,每次n/4次,共n次操作,
……
(最后一层)第k层有k次递归,每次n/2^k次,共n次操作
由于递归结束的条件是只有一个元素,所以这里的n/2^k=1 => k=logn
即递归树的深度为logn
时间复杂度=每层的操作次数*树的深度=nlogn 即:O(nlgn);
方法二:
我们用T(n)来表示时间复杂度,有:
解这个递推公式:
有代入上一个公式有
有代入上一个公式有
...
最后一层递归有代入上一个公式有
已知最后一层递归时操作次数为1,,有
带入公式得
有T(1)=0;
所以 即:O(nlgn);
方法三:
主定理求解递归式:
令a>=1和b>1是常数,f(n)是一个函数,T(n)是定义在非负整数上的递归式:
,其中n/b为向上或向下取整。那么T(n)有如下渐近界:
1、若对某个常数>0,有
,则
;
2、若,则
;
3、若对某个常数>0,有
,且对某个常数c<1和所有足够大的n有
,则
;
关于以上几种情况的解释可以看算法导论第三版P54,这里稍微解释一下:
(用来分析算法复杂度的话可以把和O看成是相同的,想要具体了解的自行百度或者我后面可能再加进来)
三种情况的每一种我们将函数f(n)与进行比较,这两个之中的较大解决定了递归式的解,大小相当的情况下则乘上一个对数因子
接下来通过这种方法来计算快排的时间复杂度:
递推公式:
主定理:
所以a=2,b=2,,对应第二种情况,所以
是不是很简单……
后面再写平均和最差吧,或者可以看这篇博文
https://www.cnblogs.com/fengty90/p/3768827.html
如果我理解的有什么问题希望您能批评指针,我会进一步学习并修改,谢谢~