Version: Next
大数乘法问题
问题:参与运算的数值或运算结果大于目前计算机能表示的范围
- 使用
字符串
表示这些数据- 那么,这些字符串之间如何进行数学运算呢?
- 按
位
进行运算,模拟手算数学的过程- 将各部分运算结果进行整合处理
大数相乘
- 按照小学竖式计算乘法的方式,在计算
n
位数之间的乘法时,需要大约进行n的平方
次个位数相乘的计算
分治思想
按照分治的思想,将两个乘数分别一分为二,那么竖式乘法变为以下形式
接下来,按 位
求和
- 时间复杂度
T(n) = 4T(n / 2) + O(n)
,根据分治法主定理可推出复杂度为O(n平方)