假设u，v为两个n bits整数 ，传统的整数相乘复杂度为n2的同阶，采用分治可将时间复杂度减少为nlog3.
将u,v分为两部分，每部分n/2 bits.
u: |--w--|--x--|
v: |--y--|--z--|
则：
u = w<< 2n/2 + x
v = y<< 2n/2 + z
u * v = wy<<n + (wz + xy)<<n/2 + xz
= wy<<n + [(w + x)(y + z) - wy - xz]<<n/2 + xz
处理后需要计算3次n/2乘法
则时间复杂度: T(n) = 3T(n/2) + bn
利用master theorem可得。
矩阵相乘也可采用类似strassen方法。
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
