快速排序最优时间复杂度O(n log n)的证明及均匀分割最优性求证

快速排序的时间复杂度由递归分割的子问题规模和每层的总处理时间共同决定，核心是理解递归式的行为：

对于长度为n的数组，快速排序的递归式为：
T(n) = T(k) + T(n-1-k) + O(n)
其中k是分割后左子数组的元素个数（范围是0 ≤ k ≤ n-1），O(n)是单次分割的时间开销。

为什么均匀分割最优？ #

我们可以从两个角度拆解：

1. 递归树的深度与总工作量 #

每次分割时，子问题的规模越接近，递归树的深度就越小：

• 均匀分割时（k = floor((n-1)/2) 或 ceil((n-1)/2)），递归树的深度是log₂n级别。每一层的所有子问题总长度之和都是n，因此每层的总处理时间是O(n)，总时间就是O(n log n)。
• 非均匀分割时，比如分割成1个元素和n-2个元素，递归树会退化成类似链表的结构，深度达到n级别。此时总处理时间是O(n) + O(n-1) + ... + O(1) = O(n²)，远慢于均匀分割的情况。

2. 数学推导验证 #

假设对于所有小于n的数组长度m，均匀分割的T(m) ≤ 任意非均匀分割的T(m)，我们可以用归纳法证明n的情况：

• 均匀分割时，T_uniform(n) = 2*T(n/2) + O(n)
• 非均匀分割时，比如分割成a和n-1-a（a ≠ n/2），T_nonuniform(n) = T(a) + T(n-1-a) + O(n)

根据归纳假设，T(a) + T(n-1-a) ≥ 2*T((a + n-1-a)/2) = 2*T((n-1)/2)，因为函数T(m)是凸函数（随着m增大，T(m)的增长速度越来越快）。因此T_nonuniform(n) ≥ T_uniform(n)，即均匀分割的时间复杂度更低。

简单来说：快速排序的时间开销和子问题的"总递归成本"直接相关，分割越均匀，子问题的递归成本总和越小，整体效率就越高。

内容的提问来源于stack exchange，提问作者Ryan