作者wilson50101 (我觉得我还不错啊)
看板Grad-ProbAsk
标题[理工] 演算法devide and conquer 105清大
时间Mon Aug 20 13:11:43 2018
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1534741905.A.174.html
1F：推 jp860316: n/2*n/2的最大长度为n，n的加减法做常数次都是O(n) 08/21 01:37
2F：→ jp860316: 长度n相乘为T(n),所以长度n/2相乘为T(n/2) 08/21 01:38
3F：→ jp860316: 所以看式子T(n)可以分成３T(n/2)+O(n) 08/21 01:40
4F：→ DLHZ: google:Karatsuba 12/04 19:04