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