algorithm - QuickSortアルゴリズムの分析

Question

クイックソートについてYouTubeでMITの講義をフォローしています。私はほとんどのアイデアを思いついたが、彼が次の点で算術級数を言ったことに固執している。

最悪の場合：T（n）= T（n-1）+ Theta（n）

彼は「それは何に等しいのか」と尋ねました。

そして彼はそれがシータ（n ^ 2）に等しいと言いました

シータ（n ^ 2）と等しく、シータ（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)ます。