作者suhorng ( )
站内Prob_Solve
标题Re: [问题] sort的时间复杂度
时间Sun Feb 5 09:14:32 2012
※ 引述《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
1F：推 mqazz1:谢谢 可以请问3T(2n/3)是怎麽来的吗? 02/05 20:09
2F：→ chunhsiang:WIKI上看一下吧 就用k导出来了而已 02/05 21:40
3F：→ chunhsiang:另外我个人觉得这题应该只能导big O吧 theta有点太过 02/05 21:50
4F：→ chunhsiang:而且答案应该会比n^2大一点 02/05 21:51
5F：→ chunhsiang:毕竟他是问最差 02/05 22:01
6F：→ suhorng:我化简错了 这答案错了 02/06 20:45
7F：→ suhorng:不过不能导theta? 02/06 21:37
8F：→ suhorng:n^{log3/(log3 - log2)} .. 不过为什麽不能用theta @@ 02/06 22:47
9F：→ chunhsiang:可以用... 只是题目问最差 给他的UPPER就差不多了 02/06 23:25
10F：→ chunhsiang:只是以改考卷人立场而以 02/06 23:27