推 assassin88:原來如此 我了解了 03/16 13:10
推 assassin88:可以順便請問第五題怎寫嗎? n^2的方法想不太出來.. 03/16 13:29
→ FRAXIS:Dynamic Programming.. 03/16 13:36
※ 引述《assassin88 (Ace)》之銘言：
: 題目：http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_98_01.pdf
: 請問一下第六題演算法大家是用什麼寫呢？
: 想不太出來XD
建一個AVL Tree，結點內除了記錄key之外還要記錄count。
如果同一個key被重複插入，就把count增加。
把所有的整數插入此樹中，然後在Inorder Traverse，就會是sorted了。
因為只有O(lgn)個相異元素，所以樹高頂多就是O(lglgn)，所以演算法
複雜度就是O(nlglgn)。
在用Decision Tree Model的時候，是假設輸入有n!個排列。
但是當相異元素只有O(lgn)個時，排列數的算法就不同了..
--
我記得還有另一種方法，只是現在忘了..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50