推 kiwidoit:感謝FRAXIS大精闢的解析^^!! 12/15 04:28
推 da0910cc: 12/19 10:36
→ da0910cc:有的資訊太少,我也不知要怎分 12/19 10:38
: ※ 引述《kiwidoit (噗嚕噗嚕)》之銘言：
: : ※ 引述《da0910cc (da0910cc)》之銘言：
: : 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-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應該也是才是。
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 140.119.162.50
: 推 kiwidoit:1-2:DP才需要嚴格要求Optimal Substructure吧@@? 12/14 21:38
Greedy Algorithm也是有Optimal Substructure，
http://en.wikipedia.org/wiki/Greedy_algorithm#Specifics
或是Greedy Choice Property，但是Bubble Sort那些演算法，
好像很難歸類成有用到這些性質。
: → kiwidoit:1-4:他是問non-constant space... 12/14 21:39
我想我解釋不夠清楚，而且寫錯解答了..
Constant space有兩種解讀方式
第一種是O(1) space，其實O(1) space能夠做的事情非常非常有限，
假設你有一個變數i，其範圍是1 ~ n，用來Traverse陣列，所以i至少
就需要O(log n) bit，所以O(1) space演算法連traverse陣列都辦不
到，更不用說排序了。
第二種是O(1) variables，就是假設每一個變數所需要的空間是O(1)
（儘管實際上不是），他實際上代表的是O(log n) space。可以參考
http://en.wikipedia.org/wiki/In-place_algorithm#In_computational_complexity
所以你用第一種解讀的話，那所有排序演算法都是non constant space。
因此答案就是所有的stable排序演算法。
如果你用第二種方法解讀，答案就是Radix sort和Count sort。
: 推 kiwidoit:1-5:其實這一題他應該要講清楚sorted跟現在要sort的順序 12/14 21:42
: → kiwidoit:是不是同向的... 12/14 21:42
因為Selection Sort的Best Case和Worst Case都是O(n^2)，
也就是說無論輸入什麼都是一樣的時間，所以任何輸入
都是Worst Case。
http://en.wikipedia.org/wiki/Sorting_algorithm
而Radix Sort和Count sort，執行時間跟輸入順序沒啥關係，
無論輸入什麼都一樣的時間，所以任何輸入都是Worst Case。
至於Bubble Sort的話，答案取決於Bubble Sort的版本，
如果Bubble Sort會偵測陣列是否已經排序好，
那麼，sorted input就不會是worst case。
反之，如果Bubble Sort不會去偵測陣列是否已經排序好，
那麼，無論輸入是什麼，Bubble Sort都會需要O(n^2)時間
，所以任何輸入都是worst case。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50