推 bernachom:謝謝您的幫忙，第2題我在翻一下課本好了 12/15 18:32
→ bernachom:因為還是想知道怎麼說明這題...謝謝幫忙 12/15 18:33
※ 引述《bernachom (Terry)》之銘言：
: 太久沒看，有點忘了
: 請教一下quicksort和matrix-chain
: 1.
: http://ppt.cc/7@j(
: http://ppt.cc/0Kan
(a)
用代入法最快:
T(n) = T(n-1) + θ(n)
= T(n-2) + θ(n-1) + θ(n)
= ...
= T(0) + θ(1) + θ(2) + ... + θ(n-1) + θ(n)
= θ(1+2+...+n)
= θ(n(n+1)/2)
= θ(n^2)
(b)
quick sort 是unstable的sort
stable的定義就是同樣的數字如果排序後順序不會變動
而quick sort會把整串數字中的前段跟後段的數字作交換
所以順序有可能會被變動
你可以自己舉個例子就看的出來了
(c)
in-place sort的定義:
In-place sort is a sorting algorithm that does not use any extra space
beyond that needed to store the input.
簡單來說就是該演算法除了輸入資料所佔的記憶體空間外
額外用到的記憶體的數量為常數個(與輸入大小無關)
基本上quick sort應該是屬於in-place
因為quick sort除了swap元素時可能會用到一個額外記憶體外
不會用到跟輸入大小有關的記憶體來重新儲存原本的元素們
: 2.
: http://ppt.cc/G-,n
這題我不知道詳細解說要怎麼說
不過簡單來說
我覺得是用這個RECURSIVE-MATRIX-CHAIN比較有效率
畢竟把所有可能矩陣相乘的方法全部列舉出來再比較肯定是比較慢
這個RECURSIVE-MATRIX-CHAIN基本上是用類似DP的方法
但可惜的是這演算法是用recursive
所以效能其實還是沒有很好
因為同樣的"子問題"會重複再算好幾次
(他這個演算法是由上而下運算)
比較好的方法應該是由下往上運算(真正的DP寫法)
如此一來"子問題"就不需要重複運算
可以讓效能變更好
...離題了
總之這題還是用RECURSIVE-MATRIX-CHAIN比全部列舉出來好.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.83