作者metalalive (想玩音樂)
看板Grad-ProbAsk
標題[理工] [DS] merge sort 觀念
時間Mon Feb 13 15:49:17 2012
想請教兩個觀念
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
推 llll5566:worst case發生在切割到最小分的時候 開始merge時 02/13 16:02
→ llll5566:每一個都要比 所以才感覺根本沒有worst case的存在 02/13 16:03
→ llll5566:因為切割完是由大到小也一樣要merge 和比較 02/13 16:04
推 rockmanray:2.使用linked list應該對complexity沒有差別 02/13 16:44
→ rockmanray:array 也是用index往後加的方式 幾乎跟link一樣 02/13 16:44