[理工] 一些交大DS

[qwer123073 (NullSpace)]

在翻考卷統整觀念
有些題目突然不會了
所以來問一下

1.For a data set of N records stored in an m-way balanced search tree,what is
the time complexity to search a key value in terms of the number of disk accesses
in the worst case?
(交大101 21題)

答案是O(log_m N)
想問怎麼推導出來的

我的想法是
因為在search的時候
最多就是走遍樹高
不過題目問的是disk access
所以不太確定是不是這麼簡單

2.想問一下shortest path tree和MST的差別

3.Heap sort for sorting problem為何不算Greedy method呢
(交大103 第8大題)


感謝~~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.234.177.5
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486278234.A.B26.html
推 Transfat: 2.shortest path tree是指經過最短路徑，MST是指weight
→ Transfat: 和最小,但路徑（經過的邊數）不一定會是最少的
→ Transfat: 1.用decision tree,每次分支下去可以分成m種（degre=m)
→ Transfat: 所以總共有N個leaf,樹高最高就log_m N
→ Transfat: 3.Greedy的性質其中一項是要能夠切成沒有overley的subpr
→ Transfat: oblem,不過Heap Sort不符合這個性質（我覺得）
→ qwer123073: 了解了~謝謝T大