[理工] 資演 成大102 sorting

[newpuma (還很新)]

首先想問一個不解的問題

Sorting 8 elements with a comparison sort requires 24 comparisons in the worst
 case.

遇到蠻多次這種題目，如果直接代n lg n好像會被題目給騙走(被騙兩次了QQ)

這題正確解法是lg(8!)嗎？然後直接把8!炸開取lg？我算出來是15.多取上限16

第二個想問的是
http://i.imgur.com/GvsOgYr.jpg
這一題是在考什麽觀念，總覺得有點鬼打牆，爬文沒看到有人問過，該不會是太簡單了QQ
我一開始看到要由小到大排列以為是河內塔，但是看一看對一堆資料由上至下做排列是in
sertion sort嗎？


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.200.66
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485199120.A.83D.html
推 FRAXIS: https://en.wikipedia.org/wiki/Pancake_sorting
→ FRAXIS: 簡單解法是 2n-3, Bill Gates 大學時設計了一個5n/3的解法
感謝 雖然還是看不太懂怎麼設計
Pancake跟下一題的bloom filter竟然是寫這年考卷才知道這個算法
突然覺得有點完蛋了囧 如果進考場看到這些陌生的算法 當下一定會傻住..
※ 編輯: newpuma (223.137.200.66), 01/24/2017 05:18:51
→ ken52011219: 認真說，考的當下除非前一兩天有翻過
→ ken52011219: 不然之前在更久之前看得 其實你根本記不住 QQ
→ ken52011219: 只能純靠之些日子下來紮實的基本功
推 AllenPaul: 所以上面第一題答案應該是true or false ?
推 a19930301: 第一題我寫T，用8 * log8算的
推 a19930301: 突然發現原po那方法才是對的，我這是錯的，這rate 不
→ a19930301: 能代值算
→ a19930301: 所以是false
推 AllenPaul: 好 我算法也跟原po一樣 參照洪毅寫法