[理工] 演算法devide and conquer 105清大

看板Grad-ProbAsk作者 (我覺得我還不錯啊)時間7年前 (2018/08/20 13:11), 編輯推噓1(1推 0噓 3→)
留言4則, 2人參與, 最新討論串1/1
http://i.imgur.com/s51qzVI.jpg
如上圖畫線處 我不太確定他是再說什麼意思 我的理解是: (u1+u2)(v1+v2)可拆成u1v1+u2v1+u1v2+u2v2 然後再配上u1v1,u2v2 因為長度為n的bit number加/減法花O(n) 所以(u1+u2)(v1+v2)-u1v1-u2v2=u1v2+u2v1總共花四次加法一次減法O(5n)=O(n) 再配上切成這三份size/2 所以就是答案那個式子 請問我這樣理解沒問題嗎？ ----- Sent from JPTT on my Asus ASUS_Z016D. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.8.106.16 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1534741905.A.174.html
推
08/21 01:37, 7年前 , 1F
n/2*n/2的最大長度為n，n的加減法做常數次都是O(n)
08/21 01:37, 1F
→
08/21 01:38, 7年前 , 2F
長度n相乘為T(n),所以長度n/2相乘為T(n/2)
08/21 01:38, 2F
→
08/21 01:40, 7年前 , 3F
所以看式子T(n)可以分成３T(n/2)+O(n)
08/21 01:40, 3F
→
12/04 19:04, , 4F
google:Karatsuba
12/04 19:04, 4F
‣ 更多 wilson50101 的文章
文章代碼(AID): #1RUasH5q (Grad-ProbAsk)