algorithm - 分析快速排序算法

Question

我正在关注 YouTube 上关于快速排序的麻省理工学院讲座。我得到了大部分的想法，但我对他所说的算术系列在以下几点感到困惑：

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

他问：“那等于什么？”

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

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

Answer 1

它是算术级数的总和， T(n) = T(n-1) + n = n + n-1 + n-2 + ... + 1 = n(n+1)/2在Theta(n^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

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