[理工] 算法devide and conquer 105清大
楼主: wilson50101 (我觉得我还不错啊) 2018-08-20 13:11:43
如上图画线处
我不太确定他是再说什么意思
我的理解是:
(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
所以就是答案那个式子
请问我这样理解没问题吗？
作者: jp860316 (courage) 2018-08-21 01:37:00
n/2*n/2的最大长度为n，n的加减法做常数次都是O(n)长度n相乘为T(n),所以长度n/2相乘为T(n/2)所以看式子T(n)可以分成３T(n/2)+O(n)