algorithm - 分析 QuickSort 算法

Question

我正在关注 YouTube 上关于快速排序的麻省理工学院讲座。我明白了大部分的想法，但我在以下几点坚持他所说的算术级数:

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

他问，“那等于什么？”

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

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

Answer 1

这是一个sum of arithmetic progression 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) 中。