作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] sort的时间复杂度
时间Sat Feb 4 18:57:52 2012
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下
时间复杂度的递回式要怎麽导呢?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.118.110.186
1F：→ suhorng:if (i+1) <= j --> 有打错吗? 02/04 19:10
已改正了 因为题目不太清楚
这些数据是别人补上的0.0
※ 编辑: mqazz1 来自: 140.118.110.186 (02/04 19:17)
2F：→ tropical72:i2a 习题里面提到的排序法？ 02/04 19:20
3F：→ tropical72:google stooge sort 应可得到一些资讯。 02/04 19:24
4F：→ suhorng:我的意思是,那输入 SORT(A, 1, 10) 不就什麽都不跑... 02/04 20:02
5F：推 DJWS:诚如楼上所言 题目若真是如此 答案就是O(1) :p 02/04 21:07
6F：→ chunhsiang:好像打错.... 02/05 21:52