作业帮如果在考研的数据结构填空题中出现快速排序的时间复杂度是填n的平方,还是n倍log以二为底n的对数
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/06 03:31:26
如果在考研的数据结构填空题中出现快速排序的时间复杂度是填n的平方,还是n倍log以二为底n的对数
如果在考研的数据结构填空题中出现快速排序的时间复杂度是填n的平方,还是n倍log以二为底n的对数
如果在考研的数据结构填空题中出现快速排序的时间复杂度是填n的平方,还是n倍log以二为底n的对数
出题人应该不会这么坑爹吧!表示只能给出下面回答：
（1）最坏时间复杂度
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个.
因此,快速排序必须做n-1次划分,第i次划分开始时区间长度为n-i+1,所需的比较次数为n-i(1≤i≤n-1),故总的比较次数达到最大值：
Cmax = n(n-1)/2=O(n2)
如果按上面给出的划分算法,每次取当前无序区的第1个记录为基准,那么当文件的记录已按递增序(或递减序)排列时,每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录,则快速排序所需的比较次数反而最多.
（2） 最好时间复杂度
在最好情况下,每次划分所取的基准都是当前无序区的"中值"记录,划分的结果是基准的左、右两个无序子区间的长度大致相等.总的关键字比较次数：
0(nlgn)
注意：
用递归树来分析最好情况下的比较次数更简单.因为每次划分后左、右子区间长度大致相等,故递归树的高度为O(lgn),而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n,故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn).
因为快速排序的记录移动次数不大于比较的次数,所以快速排序的最坏时间复杂度应为0(n2),最好时间复杂度为O(nlgn).