乘以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），但是可能还有更好的算法尚待发现。