这是我的数据结构作业中的问题之一：
假设我们有一个线性时间过程，它保证为快速排序找到一个枢轴元素，使得至少 1% 的数组小于或等于枢轴，至少 1% 大于或等于枢轴。证明快速排序将具有最坏情况复杂度 O(n lg n)。
我知道快速排序的最坏情况复杂度一般是 O(n^2)。I read that this happens when all the values of the pivot chosen is either the largest or smallest of the taken set.
我的猜测是，由于给定的条件是至少 1% 的数组大于且至少 1% 的数组小于枢轴，这消除了枢轴是集合中最小或最大元素的情况. 因此它永远不可能是 O(n^2)
这听起来正确吗？
这类问题的主要关键是表明只有 O(log(n)) 步。
理想的快速排序递归是
T(N) = 2T(N/2) + O(n)
我们可以很容易地通过主定理证明是 O(NlogN)。
O(n) 项是递归树每一层的一个因子；此外，在理想情况下，所有元素都必须在每个级别进行处理；尽管从技术上讲，大多数元素会使其在递归树中比其他元素更远，但我们可以假设不会出现“最坏情况”，并且所有元素都会在每个级别进行处理。因此，我们所要做的就是证明在您给定的假设下，递归树中最多有 O(log(N)) 个步骤。
给定您的假设，快速排序递归：
T(N) = T(N/100) + T(99N/100) + O(n).
我们可以假设 WLOG，一旦递归树的单个分支中有 99 个或更少的元素，最多只会发生恒定数量的操作来对它们进行排序（因此，O(1) * O(n) = O(n ) 操作发生在底层；递归树既不收缩也不增长）。
那么，我们如何证明整个树的最大步数呢？好吧，我们追随最不幸的元素！假设我们从 N 个元素开始。鉴于我们的假设，应该有 50 到 99 个元素构成我们实际关心的递归树级别的最后一步的最大分支。他们收到的最坏情况下的操作都是 99% 的一部分。
所以，我们最多有 99 个元素由 X 次迭代形成，被削减 1%。这应该看起来像您以前应该见过的不同的递归树，即“几何递减”树。至于数学：
99 = N*(.99)^X
99/N = (1/.99)^-X
(1/.99)^X = N/99
log_(1/.99) (1/.99)^X = log_(1/.99) N/99
X = log_(1/.99) N/99
如您所见，右边的项是 O(log(N))。所以这是递归的最大层数，每层最多做 O(N) 的工作，所以总的工作是 O(Nlog(N))。
我不确定您是否想要比这更严格（从头开始解释真正的递归证明是很多工作），但这对于大多数大学来说都是可以接受的......