[理工] 104清大資工計科

[steven013d (STEVEN)]

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
→ tedchang102: 第十一題comparison base 下有n!種可能的排序結果
→ tedchang102:  而decision tree樹高=log4!
→ steven013d: 但取上界的結果不是5嗎???
→ tedchang102: 第九題應該是lg n吧
→ tedchang102: 因為他是說比較次數，最後一層不用比，我是這樣想的
→ steven013d: 高度是lg(n!)取上界+1?已經扣過1了說
→ tedchang102: 好像是5......那就不知道為什麼是4了sorry
→ steven013d: 還是謝謝了~
→ leo258x: 10題用n進位的LSDRadix sort吧？