Justin's Words

一个简单的乘法算法

Posted on | In |

现在你要计算 7562 * 423。

也就是：

1
2
3
4
5
long firstOperand = 7562;
long secondOperand = 423;
long result = 0;
for (int i = 0; i < secondOperand; i++)
    result += firstOperand;

时间复杂度为 O(n)。

分解开来看看更简单的算法：

1
2
3
4
long firstOperand = 7562;
7562 * 423 = 7562 * (400 + 20 + 3)
            = 7562 * 400 + 7562 * 20 + 7562 * 3
            = 756200 * 4 + 75620 * 2 + 7562 * 3

看起来乘法运算更少了，代码实现下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
long firstOperand = 7562;
long firstOperand = 7562;
long secondOperand = 423;

int secondOperandLength = 1;
long result = 0;

// 计算第二个操作数的数字个数
long dummy = secondOperand;
while (dummy /= 10)
    secondOperandLength++;

for (; secondOperandLength > 0; secondOperandLength--)
{
    // 获得该环节数位上的数字，也就是最后一个数位数字
    long digit = secondOperand - (secondOperand / 10) * 10;

    for (; digit > 0; digit--)
        result += firstOperand;

    // 去掉最后一个数位
    secondOperand /= 10;
    // 基本增加数自增 10，因为第二个操作数被去掉了一位
    firstOperand *= 10;
}

这样时间复杂度为 O(logn)，看起来好很多了~

典型的增长率函数之间的关系如下：

O(1) < O(log log n) < O(log n ) < O (log^2 n ) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)