Re: [理工] [ds]一題頗困難的配合題....

[FRAXIS (喔喔)]

※ 引述《kiwidoit (噗嚕噗嚕)》之銘言：
: ※ 引述《da0910cc (da0910cc)》之銘言：
: : 標題: [理工] [ds]一題頗困難的配合題....
: : 時間: Wed Dec  7 23:19:44 2011
: : 滿有趣的題目
: : 這題跟同學討論好久
: : 每個人答案都不同
: : 想法也不同
: : 想問看看其他人的想法
: : http://ppt.cc/OE;!

其實我不知道Table Sort是什麼，有人知道嘛？

: 1-1: Quick sort, Binary tree sort
Binary Tree Sort算做D&C好像有點勉強，因為他實際上只是
把所有元素插入到BST。當然你可以說BST算是一種D&C。

另外，如果從MSB開始做Radix Sort，似乎也可以算是種D&C？

: 1-2: Bubble sort, Selection sort, Topological sort, Kruskal's Algo,
:      Prim's Algo, Dijkstra's Algo.

如果是我，我只會選Prim's和Dijkstra。
Bubble Sort那些，好像沒有很明顯的Optimal Substructure..

: 1-3: Radix sort
Count sort也是..

: 1-4: Count sort, Radiox sort
constant space的要求下，演算法連依序traverse所有元素都辦不到，所以應該是
要選None of the above。

如果題目要問的是，non-constant變數，答案就會是Count sort和Radix sort。

: 1-5: Quick sort, Binary tree sort
Bubble sort，Selection Sort，我想Shell sort也是。
另外，Count sort和Radix Sort應該也是才是。

: 1-6: Radix sort
我不懂題目到底在問啥..

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.119.162.50
推 kiwidoit:1-2:DP才需要嚴格要求Optimal Substructure吧@@?
→ kiwidoit:1-3:嗯..少打了count sort...
→ kiwidoit:1-4:他是問non-constant space...
推 kiwidoit:1-5:其實這一題他應該要講清楚sorted跟現在要sort的順序
→ kiwidoit:是不是同向的...