資料結構 習題

(1)Multiplying two n bit numbers  u and v straightforwardly requires O(n^2) steps.By using the divide-and-conquer approach,we can split the number into equal parts and compute the product by the following method:uv = (a*2^n/2+b)(c*2^n/2+d)=ac*2^n+(ad+bc)*2^n/2+bdIf ad+bc is computed as (a+b)(c+d)-ac-bd,what is the computing time?
(2)Design an O(nlogn) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
以上兩題都是課本後面的練習題 題目連意思都不太懂
...

瀏覽完整內容，請先 註冊 或 登入會員

poorpoorpoor

第一題答案是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)
關鍵字都給你了，希望你能多研究...

瀏覽完整內容，請先 註冊 或 登入會員