乘以2個鏈表代表非常大的數字，可能的最低複雜度？

Question

我有2個鏈表，表示非常大的數字（不能保存在除鏈接列表以外的其他任何內容中）。 我有一個複雜度爲O（n）的Add方法。 我想知道是否有可能以任何方式乘2號沒有整個列表轉換爲字符串/ INT /長（計算上的列表中，如果可能的話），並保持在一個複雜度O（N^2 ）。

現在，不管我怎麼努力，我得到一個爲O（n^3）的複雜性，它不是足夠好。

感謝所有幫助。

Answer 1

的"long multiplication"算法大多數西方人在學校裏學到的已經給你O（N²）的複雜性，所以也許你能解釋一下你用的是什麼算法。

有算法複雜度較低：Karatsuba,Tom-Cook和Schönhage–Strassen algorithm。最後一個知道迄今爲止已知的最低複雜度O（n log n log log n），但是可能還有更好的算法尚待發現。