我们使用常规的快速排序算法。选择的枢轴是中位数，但是要找到中位数，需要采用Theta(n^{2006/2005})最差情况。
为什么算法的最坏情况相等Theta(n^{2006/2005}) 而不同 Theta(n^{2006/2005} * logn)？
首先，你要明白，每个“迭代”不走N^2006/2005这里N是原始数组的大小，其实-因为这是一个超线性函数，发现在2两半阵列的中位数比在大发现它更容易大批。
为了正式证明这一点，我们将首先定义递归复杂度公式：（为简单起见，我们假设中位数取正值n^2006/2005，但是很容易修改的上限C*n^2006/2005。）
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。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句