Re: [問題] sort的時間複雜度

[suhorng ( )]

※ 引述《mqazz1 (無法顯示)》之銘言：
: SORT(A, i, j)
: {
:         if A[i] > A[j]
:         then exchange A[i] and A[j]
:         if ( (i+1) <= j )
                     >=
:         then return
:         k = (j-i+1)/3
:         SORT(A, i, j-k)
:         SORT(A, i+k, j)
:         SORT(A, i, j-k)
: }
: 請問這個SORT在worst case下
: 時間複雜度的遞迴式要怎麼導呢?
: 謝謝

We can notice that the algorithm split the array into three approximately
equal size aparts. So

T(n) = 3T(2n/3) + Θ(1)

By applying the Master Theorem we see that T(n) = Θ(n^2)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.217.33.242
推 mqazz1:謝謝 可以請問3T(2n/3)是怎麼來的嗎?
→ chunhsiang:WIKI上看一下吧 就用k導出來了而已
→ chunhsiang:另外我個人覺得這題應該只能導big O吧 theta有點太過
→ chunhsiang:而且答案應該會比n^2大一點
→ chunhsiang:畢竟他是問最差
→ suhorng:我化簡錯了 這答案錯了
→ suhorng:不過不能導theta?
→ suhorng:n^{log3/(log3 - log2)} .. 不過為什麼不能用theta @@
→ chunhsiang:可以用... 只是題目問最差 給他的UPPER就差不多了
→ chunhsiang:只是以改考卷人立場而以