快速排序的最坏情况是，当您选择枢轴元素时，该元素是数组中的最小或最大元素，以便所有剩余的元素进入分区的一侧，而分区的另一侧为空。在这种情况下，非空分区的大小为（n-1），并且它需要线性时间（对于某些常数k> 0为kn）进行分区，因此递归关系为

  

T（n）= T（n-1）+ T（0）+ kn

如果我们为某些常数a，b，c猜测T（n）=an²+ bn + c，那么我们可以代入：

  

an²+ bn + c = [a（n-1）²+ b（n-1）+ c] + [c] + kn

其中两个方括号项分别为T（n-1）和T（0）。通过扩展方括号和等式系数，我们得到

  

an²=an²

     

bn = -2an + bn + kn

     

c = a-b + 2c

因此，存在一系列由c = T（0）参数化的解，其中a = k / 2和b = k / 2 + c。该系列解决方案可以完全按照以下方式编写

  

T（n）=（k / 2）n²+（k / 2 + c）n + c

不仅是O（n²），而且是Ө（n²），这意味着运行时间是一个二次函数，不仅限于二次函数。请注意，只要k> 0（即分区步骤的确花费了正数的时间），c的实际值就不会改变函数的渐近行为。

我找到了我的问题的答案，上一个等式的延续是，

如果是这样