作者EdisonX (闭上眼的鱼)
站内Prob_Solve
标题[问题] 请教这份大数乘法复杂度
时间Wed Jan 2 10:33:51 2013
在不碰 fft , 搞效能时想到的一招,
但不确定 Big-O 为何, 也不确定这种方式会比较快
(与 Cij = ΣΣAi*Bj 比)
想请教各位先进。
---
假设以 100 为进位，计算 1234 * 5678
1234 * 5678
= (12*100 + 34) * (56 * 100 + 78)
= { 12*56*10000 + (12*78+34*56)*100 + 34*78 }
[00][00][12][34]
x [00][00][56][78]
-----------------------
(0) rst = [00][00][00][00]
(1) 34*78 = 2652
rst = [00][00][00][2652]
= [00][00][26][52]
(2) 12*78+34*56 = 2840
rst = [00][00][26+2840][52]
= [00][00][2866][52]
= [00][28][66][52]
(3) 12*56 = 672
rst = [00][28+672][66][52]
= [00][700][66][52]
= [07][00][66][52]
整个流程可以再用递回不断分割，分割过程是 O(logn)，
但最後的相乘还要是 O(n^2)，请教整体的 Big-O 为何？
谢谢各位先进不吝赐教，感激不尽。
--
~ 这辈子与神手无缘
我只好当神兽了 ~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 180.177.76.161
1F：推 FRAXIS:你分解成4个小问题 每个小问题都是原本的一半 所以是O(n^2) 01/02 10:42
2F：→ FRAXIS:你可以参考一下 Karatsuba algorithm 01/02 10:43
3F：→ EdisonX:原来如此,看来我的想法似乎没助益,谢谢 F 大 :) 01/02 10:57
4F：→ EdisonX:疑！我查一下 Karatsuba algorithm, 真的有助益, 感谢 :) 01/02 11:00