演算法 Divide and conquer

看板Grad-ProbAsk作者 (CJentalL)時間4年前 (2021/12/11 13:20), 編輯推噓10(10推 0噓 21→)
留言31則, 4人參與, 4年前最新討論串1/1
https://i.imgur.com/cAHPDBO.jpg
如題 清大這題把Bit切分成前後半 又特別講解要做出u1v2+u2v1 原因是什麼呀 這樣跟u1v1直接乘有什麼差別呢 ---- Sent from BePTT on my iPhone 11 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.97.138 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1639200005.A.6A1.html
推
12/11 14:03, 4年前 , 1F
12/11 14:03, 1F
→
12/11 14:03, 4年前 , 2F
你參考看看
12/11 14:03, 2F
推
12/11 14:16, 4年前 , 3F
TL;DR: 因為 u1v2 和 u2v1 的位移都是 n/2，所以併在一起算
12/11 14:16, 3F
→
12/11 14:42, 4年前 , 4F
請問為何前半段的u1 v1反而不成上權重呢
12/11 14:42, 4F
→
12/11 14:42, 4年前 , 5F
後半段的數比較小反而乘上權重
12/11 14:42, 5F
推
12/11 14:44, 4年前 , 6F
因為 u1v1 不用位移呀
12/11 14:44, 6F
推
12/11 14:48, 4年前 , 7F
12/11 14:48, 7F
→
12/11 14:50, 4年前 , 8F
阿，我好像知道我哪裡弄混你了
12/11 14:50, 8F
→
12/11 14:50, 4年前 , 9F
我的算式裡 u2 和 v2 是比較高的位元
12/11 14:50, 9F
→
12/11 14:51, 4年前 , 10F
跟題目反過來
12/11 14:51, 10F
→
12/11 14:55, 4年前 , 11F
阿我懂了 謝謝大大講解
12/11 14:55, 11F
→
12/11 14:55, 4年前 , 12F
你是把U2 V2當作前半段對吧
12/11 14:55, 12F
推
12/11 14:56, 4年前 , 13F
嘿嘿沒錯
12/11 14:56, 13F
→
12/11 14:57, 4年前 , 14F
那我另外想請問
12/11 14:57, 14F
→
12/11 14:57, 4年前 , 15F
我貼文的圖片裡
12/11 14:57, 15F
→
12/11 14:57, 4年前 , 16F
最後Merge階段是thetaN
12/11 14:57, 16F
→
12/11 14:57, 4年前 , 17F
那是因為各but相加嗎
12/11 14:57, 17F
推
12/11 14:59, 4年前 , 18F
可以這樣說。在利用遞迴算出那三組算式後，剩下的就只剩加
12/11 14:59, 18F
→
12/11 14:59, 4年前 , 19F
減法跟位元位移的運算了，這些可以在 theta(N) 內算出
12/11 14:59, 19F
→
12/11 15:02, 4年前 , 20F
Bit
12/11 15:02, 20F
→
12/11 15:05, 4年前 , 21F
不過感覺這題最Tricky的地方是在
12/11 15:05, 21F
→
12/11 15:05, 4年前 , 22F
我怎麼想的到u1v2+u2v1 可以用(u1+u2 )(v1+v2)乘出來
12/11 15:05, 22F
→
12/11 15:05, 4年前 , 23F
雖然這不是很難
12/11 15:05, 23F
→
12/11 15:05, 4年前 , 24F
但一開始真的想不到可以這樣
12/11 15:05, 24F
推
12/11 15:07, 4年前 , 25F
我 conquer 這題的思考過程，是先用最原始的方法算，然後看
12/11 15:07, 25F
→
12/11 15:07, 4年前 , 26F
哪裡是可以化簡的。
12/11 15:07, 26F
→
12/11 15:08, 4年前 , 27F
再來就是靠想像力了
12/11 15:08, 27F
推
12/11 15:10, 4年前 , 28F
分解再重組，鋼之鍊金術師都有教
12/11 15:10, 28F
推
12/11 16:25, 4年前 , 29F
我的想法是u1v2和u2v1的位移量是一樣的 所以可以直接
12/11 16:25, 29F
→
12/11 16:25, 4年前 , 30F
算他們的和
12/11 16:25, 30F
推
12/11 20:35, 4年前 , 31F
karatsuba變形吧，當場沒看過真的很難想到
12/11 20:35, 31F
‣ 更多 j12345453 的文章
文章代碼(AID): #1Xj3K5QX (Grad-ProbAsk)