问题描述

请设计一个有效的算法，可以进行两个n位大整数的乘法运算
image.png
image.png
细节问题：
两个XY的复杂度都是O(n**log3**)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案

  • 如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。
  • 最终的，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。
  • 是否能找到线性时间的算法？？？目前为止还没有结果。