[理工] 104清大資工計科

看板Grad-ProbAsk作者 (STEVEN)時間10年前 (2016/01/18 14:45), 10年前編輯推噓0(009)
留言9則, 3人參與, 最新討論串1/1
http://imgur.com/9WL9oOu
第10,11題 10.是使用counting sort嗎?複雜度有可能到n^2? 11.不知道該如何去求解? http://imgur.com/svtEquu
http://imgur.com/gJxJUW5
第9題中的a小題 單純分析adjust()複雜度 應該是多少? 謝謝各位! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.27.137.221 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1453099552.A.35D.html ※ 編輯: steven013d (110.27.137.221), 01/18/2016 14:58:35

01/18 14:59, , 1F
第十一題comparison base 下有n!種可能的排序結果
01/18 14:59, 1F

01/18 14:59, , 2F
而decision tree樹高=log4!
01/18 14:59, 2F

01/18 15:02, , 3F
但取上界的結果不是5嗎???
01/18 15:02, 3F

01/18 15:10, , 4F
第九題應該是lg n吧
01/18 15:10, 4F

01/18 15:12, , 5F
因為他是說比較次數,最後一層不用比,我是這樣想的
01/18 15:12, 5F

01/18 15:27, , 6F
高度是lg(n!)取上界+1?已經扣過1了說
01/18 15:27, 6F

01/18 15:29, , 7F
好像是5......那就不知道為什麼是4了sorry
01/18 15:29, 7F

01/18 15:32, , 8F
還是謝謝了~
01/18 15:32, 8F

01/27 17:26, , 9F
10題用n進位的LSDRadix sort吧?
01/27 17:26, 9F
文章代碼(AID): #1Md8eWDT (Grad-ProbAsk)