[問題] sort的時間複雜度

[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下

時間複雜度的遞迴式要怎麼導呢?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186
→ suhorng:if (i+1) <= j   -->   有打錯嗎?
已改正了 因為題目不太清楚
這些數據是別人補上的0.0
※ 編輯: mqazz1          來自: 140.118.110.186      (02/04 19:17)
→ tropical72:i2a 習題裡面提到的排序法？
→ tropical72:google stooge sort 應可得到一些資訊。
→ suhorng:我的意思是,那輸入 SORT(A, 1, 10) 不就什麼都不跑...
推 DJWS:誠如樓上所言  題目若真是如此  答案就是O(1) :p
→ chunhsiang:好像打錯....