Re: [問題] 關於在這種情況之下sort的複雜度
根據你說的兩個題目的特性 :
→ lO:其實我例子舉得不好 負數是連在一起沒錯 但是不一定只有一段
→ lO:正數一定是連續且排序的 只不過也是一段一段的
再回頭看看你給的例子 :
1,2,3,4,5,6,7,8,-5,-6,-7,-4,-2,-8,-1,9,10,11,12,13,14,15
可以把正數、負數分開蒐集起來, 各自形成新的序列
正序列 : 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
負序列 : -5,-6,-7,-4,-2,-8,-1
掃描的過程, 時間複雜度為 O( n ). (假設原本的序列長度為 n)
上面的正序列已經排過了, 所以不要對他做任何處理, 我們只需要排負序
列的部份, 這時候如果只是單純要排整數, 用快速排序就能解決了, 假設
負序列的長度為 w, 排序的總時間複雜度只有 O( wlogw )
最後最後, 你要的結果應該是 : "排序後的負序列" | "正序列" 兩序列
接起來的結果, 這個步驟時間複雜度是 O( n )
總共的時間複雜度為 : O( n ) + O( wlogw ) + O( n ), 這時候就由負
數佔原序列的比例來決定程式的執行速度了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.121.197.115
※ 編輯: loveme00835 來自: 140.121.197.115 (06/28 17:32)
推
06/28 17:38, , 1F
06/28 17:38, 1F
→
06/28 17:42, , 2F
06/28 17:42, 2F
推
06/28 17:45, , 3F
06/28 17:45, 3F
→
06/28 17:45, , 4F
06/28 17:45, 4F
→
06/28 17:45, , 5F
06/28 17:45, 5F
→
06/28 17:46, , 6F
06/28 17:46, 6F
→
06/28 17:46, , 7F
06/28 17:46, 7F
→
06/28 17:47, , 8F
06/28 17:47, 8F
推
06/28 17:49, , 9F
06/28 17:49, 9F
→
06/28 17:52, , 10F
06/28 17:52, 10F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
