看板 Grad-ProbAsk 關於我們 聯絡資訊
https://i.imgur.com/BoXvyWT.jpg
https://i.imgur.com/lSNOKDT.jpg
請問K1和K2是什麼? 我看不是很懂題目的意思QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.147.84 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1550919839.A.140.html
sooge: 同問 看不懂 雖然前面有兩篇問過了不過都沒講到重點的樣子. 02/23 21:29
sooge: .. data record的長度到底是什麼 02/23 21:29
AliennC: 個人淺見,母題題意是用K1, K2 作為 data 的索引,可以 02/23 22:15
AliennC: 想像成 K 是座號而 data 是同學名字,樓上有疑問的 data 02/23 22:15
AliennC: 長度就類似名字長度。 data 和對應的 K 是綁在一起的, 02/23 22:15
AliennC: 排序用 K 來排,但實際上目的是要整理 data set,可以想 02/23 22:15
AliennC: 像成我們要把一個班級的同學排成一列需要有座號的協助去 02/23 22:15
AliennC: 對應,至於怎麼排序就是子題要問的問題,另外要注意母體 02/23 22:15
AliennC: 有聲明沒特別講的話各子題的 K 是互不相關的 02/23 22:15
sooge: 那為什麼4-6答案是D E和F不行嗎 data長度會讓E和F不好實施 02/23 22:37
sooge: 嗎 02/23 22:37
AliennC: 呃我不知道答案,純粹分享想法你加減參考,不敢說我一定 02/23 23:02
AliennC: 對,有錯再請指教。這題 data 的數量滿多的,如果一個 s 02/23 23:02
AliennC: et 裡面稍微多塞一點東西(例如 data 長一點之類)就可能 02/23 23:02
AliennC: 會超出一個 page,這時候如果要 swap 兩個不同 page 內 02/23 23:02
AliennC: 的資料就會很耗時,因此像 quick sort 這種需要從兩端去 02/23 23:02
AliennC: 追蹤的算法勢必會有上面的問題。另一方面,merge sort 02/23 23:02
AliennC: 因為不是 in-place,也就是要把整份資料庫複製一份在外 02/23 23:02
AliennC: 面才能執行,這也是很花資源的行為。heap sort 同 quick 02/23 23:02
AliennC: sort,heap sort 通常用 array 之類這種連續的資料結構 02/23 23:02
AliennC: ,也就是說在調整子樹中,一直往下找可能會穿越 page, 02/23 23:02
AliennC: 而且調整子樹次數也很多 02/23 23:02
AliennC: 所以 heap sort 也不適用在大型資料庫的排序 02/23 23:05
sooge: 所以照這樣說的話 如果只是資料量多但data size不大的話用q 02/23 23:42
sooge: uick sort從兩邊去追縱的話很像是最適合的 02/23 23:42
sooge: 謝謝你 解釋超詳細的 02/23 23:42
AliennC: 要看用途吧,例如 os 中比較要求 worst case 也就是要求 02/24 00:15
AliennC: 穩定性的時候會傾向 merge sort,何況 quick sort 還有 02/24 00:15
AliennC: unstable 這個致命缺點,所以很難斷定什麼時候用哪個絕 02/24 00:15
AliennC: 對比較好 02/24 00:15