作者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/cn.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