算法 Divide and conquer j12345453 PTT批踢踢实业坊

楼主: j12345453 (CJentalL) 2021-12-11 13:20:03

https://i.imgur.com/cAHPDBO.jpg
如题
清大这题把Bit切分成前后半
又特别讲解要做出u1v2+u2v1
原因是什么呀
这样跟u1v1直接乘有什么差别呢

作者: VF84 (Jolly Roger) 2021-12-11 14:03:00

https://imgur.com/a/mSGW38E你参考看看TL;DR: 因为 u1v2 和 u2v1 的位移都是 n/2，所以并在一起算

楼主: j12345453 (CJentalL) 2021-12-11 14:42:00

请问为何前半段的u1 v1反而不成上权重呢后半段的数比较小反而乘上权重

作者: VF84 (Jolly Roger) 2021-12-11 14:44:00

因为 u1v1 不用位移呀https://imgur.com/a/OxCOHgm阿，我好像知道我哪里弄混你了我的算式里 u2 和 v2 是比较高的位元跟题目反过来

楼主: j12345453 (CJentalL) 2021-12-11 14:55:00

阿我懂了谢谢大大讲解你是把U2 V2当作前半段对吧

作者: VF84 (Jolly Roger) 2021-12-11 14:56:00

嘿嘿没错

楼主: j12345453 (CJentalL) 2021-12-11 14:57:00

那我另外想请问我贴文的图片里最后Merge阶段是thetaN那是因为各but相加吗

作者: VF84 (Jolly Roger) 2021-12-11 14:59:00

可以这样说。在利用递回算出那三组算式后，剩下的就只剩加减法跟位元位移的运算了，这些可以在 theta(N) 内算出

楼主: j12345453 (CJentalL) 2021-12-11 15:02:00

Bit不过感觉这题最Tricky的地方是在我怎么想的到u1v2+u2v1 可以用(u1+u2 )(v1+v2)乘出来虽然这不是很难但一开始真的想不到可以这样

作者: VF84 (Jolly Roger) 2021-12-11 15:07:00

我 conquer 这题的思考过程，是先用最原始的方法算，然后看哪里是可以化简的。再来就是靠想像力了分解再重组，钢之炼金术师都有教

作者: NCTUCKCurry (CKNCTUCurry) 2021-12-11 16:25:00

我的想法是u1v2和u2v1的位移量是一样的所以可以直接算他们的和

作者: joywilliamjo (joywilliamjoy) 2021-12-11 20:35:00

karatsuba变形吧，当场没看过真的很难想到

继续阅读