QuickSort算法分析

Question

我正在听麻省理工学院关于YouTube的关于快速排序的讲座。我得到了大部分的想法，但我在以下几点上被他所说的算术级数卡住了：

最坏情况: T(n) = T(n-1) + Theta(n)

他问道：“这等于什么？”

然后他说它等于Theta(n^2)

为什么它等于Theta(n^2)而不等于Theta(n)？

Answer 1

这是一个位于Theta(n^2)中的sum of arithmetic progression T(n) = T(n-1) + n = n + n-1 + n-2 + ... + 1 = n(n+1)/2

您也可以通过归纳获得它，假设Theta(n)代表n (为了简单起见，可以使用相同的方法进行修改)：

Hypothesis: T(n) = n(n+1)/2
Base: T(1) = 1*2/2 = 1
Step: 
T(n) = T(n-1) + n <= (*) (n-1)*n/2 + n = 
     = (n^2 -n)/2 + 2n/2 = (n^2-n + 2n)/2 =
     =  (n^2 +n) /2 = n(n+1)/2
(*) induction hypothesis

这向我们展示了确实在Theta(n^2)中的T(n) = n(n+1)/2。