快速排序算法在平均情况下的时间复杂度为 求详

发布于:2019-05-12   编辑:admin 浏览:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  而 T(1) = 1 (表示长度为1的序列无法划分子序列,只需要1的时间即可)

  以上是最优情况的推导,因此快速排序在最优情况下其排序时间为O(nlogn),通常平均情况

  在最坏情况下其会退化为冒泡排序,T(n) = T(n - 1) + n (每次选取的元素只能将序列划分为

  因此T(n) = n * (n-1) / 2 相当于O(n^2)追问n被不断二分最终只能二分logn次 什么意思?追答在最优的情况下,即每次二分序列时都将序列平均的分为两部分,此时n被不断二分最终只能二分logn次。

  意思就是在最优的情况下对n进行二分时最多二分m次即会出现2^m个全为1的序列。

  其中m即等于logn,所以T(n) = nT(1) + nlogn = n + nlogn

  n个元素的排序条件为T(n)= 2 * T(n / 2个)+ N(表示序列分为两个子序列中的n的长度,每个子序列需要到T(n / 2个)

  以上是派生的理想情况下,快速排序排序在最佳的情况下,时间为O(nlogn)通常平均

  在最坏的情况下,它会沦为冒泡排序,T(N)= T(n - 1个)+ N(每次选择元素序列分为

  展开全部正如归并排序一样,快速排序也是递归的,因此,他的分析需要求解一个递推公式。我们将对快速排序进行这种分析,假设有一个随机的枢纽元(不用三数中值分割法),对一些小的文件也不使用截止范围。和归并排序一样,取T(0)=T(1)=1,快速排序的运行时间等于两个递归调用的运行时间加上花费在分割上的限行时间(枢纽元的选取仅花费常数时间)。我们得到基本的快速排序关系:

  枢纽元始终是最小元素。此时i=0,如果我们忽略无关紧要的 T(0)-1,那么递推关系为