Version: Next

大数乘法问题

问题:参与运算的数值或运算结果大于目前计算机能表示的范围

  • 使用字符串表示这些数据
  • 那么,这些字符串之间如何进行数学运算呢?
    • 进行运算,模拟手算数学的过程
    • 将各部分运算结果进行整合处理

大数相乘

  • 按照小学竖式计算乘法的方式,在计算 n 位数之间的乘法时,需要大约进行 n的平方 次个位数相乘的计算

分治思想

按照分治的思想,将两个乘数分别一分为二,那么竖式乘法变为以下形式

接下来,按 求和

  • 时间复杂度 T(n) = 4T(n / 2) + O(n),根据分治法主定理可推出复杂度为 O(n平方)