[理工] [DS] merge sort 觀念

看板Grad-ProbAsk作者 (想玩音樂)時間14年前 (2012/02/13 15:49), 編輯推噓2(2推 0噓 3→)
留言5則, 2人參與, 最新討論串1/1
想請教兩個觀念 1. merge sort 的 worst case time complexity 跟 base case 的一樣,那 worst case 會發生在什麼情況下呢? 2. merge sort 在合併2個sorted sub sequence 之時 這2個 sub sequence 使用 array或者使用 linked list 對 time complexity 與 space ocmplexity 有什麼影響 3Q -- No time to pray.... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 124.8.77.72
推
02/13 16:02, , 1F
worst case發生在切割到最小分的時候 開始merge時
02/13 16:02, 1F
→
02/13 16:03, , 2F
每一個都要比 所以才感覺根本沒有worst case的存在
02/13 16:03, 2F
→
02/13 16:04, , 3F
因為切割完是由大到小也一樣要merge 和比較
02/13 16:04, 3F
推
02/13 16:44, , 4F
2.使用linked list應該對complexity沒有差別
02/13 16:44, 4F
→
02/13 16:44, , 5F
array 也是用index往後加的方式 幾乎跟link一樣
02/13 16:44, 5F
‣ 更多 metalalive 的文章
文章代碼(AID): #1FEC20pv (Grad-ProbAsk)