1. PTT
  2. Prob_Solve

[問題] 請教這份大數乘法複雜度

作者: EdisonX (卡卡獸)   2013-01-02 10:33:51
在不碰 fft , 搞效能時想到的一招,
但不確定 Big-O 為何, 也不確定這種方式會比較快
(與 Cij = ΣΣAi*Bj 比)
想請教各位先進。
作者: FRAXIS (喔喔)   2013-01-02 10:42:00
你分解成4個小問題 每個小問題都是原本的一半 所以是O(n^2)你可以參考一下 Karatsuba algorithm
作者: EdisonX (卡卡獸)   2013-01-02 10:57:00
原來如此,看來我的想法似乎沒助益,謝謝 F 大 :)疑！我查一下 Karatsuba algorithm, 真的有助益, 感謝 :)
繼續閱讀
2個程序的cpu執行比? 3個字組 udp checksum為?stephenth[問題] Suffix Tree 原始論文問題rifizRe: [問題] 面試問到的問題...LeonRe: [問題] 面試問到的問題...LeonRe: [問題] 面試問到的問題...DJWSRe: [問題] 面試問到的問題...LeonRe: [問題] 面試問到的問題...FavoniaRe: [問題] 面試問到的問題...LeonRe: [問題] 面試問到的問題...FavoniaFw: [問題] 面試問到的問題...wangtrying

Links booklink

Contact Us: admin [ a t ] ucptt.com