# 解析 ↵

一眼丁真，直接按照乘法的加法定义来做

00const mul = (a: number, b: number): number => {
01  if (b === 0) return 0;
02  return a + mul(a, b - 1);
03}

但是，这样计算复杂度是

O (n)

而且，数量级稍微大一点就栈溢出了，如何优化？

注意到按加法定义计算 3 * 14 的计算要跑 14 次

3 * 14 = 一共 14 次 3 + 3 + \dots + 3

而通过除 2 乘 2 的时候:

3 * 14 3 * 7 = 3 * (14/2) * 2 = 3 * 7 * 2 = 仅需计算 3*7 3 * 7 + 3 * 7 = 一共 7 次 3 + 3 + \dots + 3

也就是说

3 * 14

实际就是计算

3 * 7

, 最后其实就只需要 7 步, 实现了步骤规模的缩小, 时间复杂度可以达到逆天的

O (l o g_{n})

实际执行速度相当快

00const mul = (a, b) => {
01  if (b === 0) return 0;
02  if (b % 2 === 1) return a + mul(a, b - 1);
03  const temp = mul(a, b / 2);
04  return temp + temp; // 或者 temp * 2 或者 temp << 2
05}

我是在 SICP 这本书看到的这个问题，如果你正在手搓 CPU 刚好需要实现乘法，不妨试试上面的思路去优化，注意里面的 *2 /2 其实都是位运算，包括判断奇偶数也可以走位运算实现。

更深一步的思考：递归展开后其实呈现了一种树状结构，也许这样的树结构里会蕴含着优化思路