演算法 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變形吧，當場沒看過真的很難想到

繼續閱讀