Re: [問題] sort的時間複雜度
看板Prob_Solve (計算數學 Problem Solving)作者suhorng ( )時間12年前 (2012/02/05 09:14)推噓1(1推 0噓 9→)留言10則, 3人參與討論串2/2 (看更多)
※ 引述《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
推
02/05 20:09, , 1F
02/05 20:09, 1F
→
02/05 21:40, , 2F
02/05 21:40, 2F
→
02/05 21:50, , 3F
02/05 21:50, 3F
→
02/05 21:51, , 4F
02/05 21:51, 4F
→
02/05 22:01, , 5F
02/05 22:01, 5F
→
02/06 20:45, , 6F
02/06 20:45, 6F
→
02/06 21:37, , 7F
02/06 21:37, 7F
→
02/06 22:47, , 8F
02/06 22:47, 8F
→
02/06 23:25, , 9F
02/06 23:25, 9F
→
02/06 23:27, , 10F
02/06 23:27, 10F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
