推 jp860316: n/2*n/2的最大長度為n，n的加減法做常數次都是O(n) 08/21 01:37
→ jp860316: 長度n相乘為T(n),所以長度n/2相乘為T(n/2) 08/21 01:38
→ jp860316: 所以看式子T(n)可以分成３T(n/2)+O(n) 08/21 01:40
→ DLHZ: google:Karatsuba 12/04 19:04
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