作者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