修改后的快速排序算法的时间复杂度是多少？

Question

我们使用常规的快速排序算法。选择的枢轴是中位数，但为了找到中位数，它需要 Theta(n^{2006/2005}) 最坏的情况。

为什么算法的最坏情况等于Theta(n^{2006/2005}) 而不是 Theta(n^{2006/2005} * logn)？

Answer 1

首先，您需要了解每个“迭代”并不需要 N^2006/2005，其中 N 是原始数组的大小，事实上 - 因为这是一个超线性函数，找到在数组的两半中找到中位数比在大数组中找到它更容易。

为了正式证明它，我们首先定义递归复杂度公式：（为简单起见，我们假设中位数恰好取n^2006/2005，但很容易将其修改为[=16=的上限].)

T(n) = n^2006/2005 + 2T(n/2)

现在，我们可以用归纳法证明

T(n) <= 2* n^2006/2005

这里的基本子句对于 n 足够小的值来说是微不足道的。
假设每个 k<n，假设 T(k) <= 2*(n/2)^2006/2005 成立。

T(n) = n^2006/2005 + 2T(n/2) <= (i.h.) 
     <= n^2006/2005 + 2*(2*(n/2)^2006/2005) =
     = n^2006/2005 + 4 * (n/2)^2006/2005 =
     = (*) 2^(2004/2005) *n^(2006/2005) + n^(2006/2005)
     <= 2*n^(2006/2005)

(*) 等式来自 wolfram alpha，您也可以使用公式中的一些代数推导出它。

另请注意，这与排序为 Omega(nlogn) 的事实并不矛盾，因为 n^(1+epsilon) > nlogn 对应每个 epsilon>0，并且 n 的值足够大。

修改后的快速排序算法的时间复杂度是多少？

What is the time complexity of a modified quick sort algorithm?

arrays

sorting

algorithm

big-o

time-complexity