[問題] 請教這份大數乘法複雜度
看板Prob_Solve (計算數學 Problem Solving)作者EdisonX (閉上眼的魚)時間12年前 (2013/01/02 10:33)推噓1(1推 0噓 3→)留言4則, 2人參與討論串1/1
在不碰 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
推
01/02 10:42, , 1F
01/02 10:42, 1F
→
01/02 10:43, , 2F
01/02 10:43, 2F
→
01/02 10:57, , 3F
01/02 10:57, 3F
→
01/02 11:00, , 4F
01/02 11:00, 4F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
