伊莉討論區

標題: 資料結構習題 [打印本頁]

作者: beginning34 時間: 2011-12-19 08:35 PM 標題: 資料結構習題

提示: 作者被禁止或刪除內容自動屏蔽

作者: poorpoorpoor 時間: 2011-12-23 11:50 PM

第一題答案是O(n^(log_2(3)))大約等於O(n^1.58)
比較簡單的想法是每次對乘從四次變成三次O(n^(log_2(4)))=O(N^2)降到O(n^(log_2(3)))
真的要證明就要列出複雜度的遞迴式解開
O(n)=3O(n/2)+theta(n)解法就不詳述
第二題是求最長單調遞增子序列
O(nlogn)的算法很經典GOOGLE一定有，大致上是GREEDY+二分搜
也可以搭配資料結構線段樹來達到O(nlogn)
關鍵字都給你了，希望你能多研究

歡迎光臨伊莉討論區 (http://a401.file-static.com/)