小探险家学算法

Appearance

1. 谁算得快？（复杂度入门） ​

知识点：时间复杂度入门 —— O(1)、O(n)、O(log n) 三个量级

项目：求和竞赛 + 猜数字

故事开场：高斯与 100 个小球 ​

很久以前，老师给全班出了一道题："把 1 到 100 加起来，等于多少？"

其他同学都低着头，一个数一个数地加：1 + 2 = 3，3 + 3 = 6，6 + 4 = 10……

只有一个小男孩，几秒钟后举起了手："老师，是 5050。"

他就是高斯——后来成了世界上最伟大的数学家之一。

他是怎么做到的？他发现：

1  +  2  +  3  + ... + 100
100 + 99 +  98 + ... +  1

把上下两行相加，每一列都是 101，一共有 100 列：

101 × 100 ÷ 2 = 5050

所以，从 1 加到 n，可以一步算出来：

(1 + n) × n ÷ 2

今天，我们要用计算机来一场真正的比赛：

比赛题目：把 1 加到 10 亿（1000000000），谁先算完谁赢。

一个选手是我们写代码时"第一个想到的办法"，另一个选手是高斯的办法。 我们来看看，谁更快。

笨办法先行：让计算机"老老实实"地加 ​

先写"第一个想到的办法"：用循环，从 1 一直加到 10 亿。

新建一个文件，比如 sum.ts，敲入下面的代码：

ts
// 慢方法：老老实实，一个一个加
function sumSlow(n: number): number {
  let total = 0
  for (let i = 1; i <= n; i++) {
    total = total + i   // 每来一个数，就加一次
  }
  return total
}

// 计时开始
console.time("慢方法")
const result = sumSlow(1000000000)
console.timeEnd("慢方法")

console.log("答案：" + result)

在终端里运行它：

bash
node sum.ts

盯着屏幕看。你会发现，程序并没有立刻给出答案——它"想"了一会儿。

在我这台电脑上，输出了这样两行（你电脑上的耗时数字可能不一样，这不重要）：

慢方法: 1.6s
答案：500000000067109000

嗯……这个答案，对不对呢？

我们先用高斯公式算一算：(1 + 1000000000) × 1000000000 ÷ 2 = 500000000500000000。

咦，慢方法算出来的 500000000067109000，和正确答案差了一点点！

先别急，把高斯的办法也写进去：

ts
// 快方法：高斯一步算出答案
function sumFast(n: number): number {
  return ((1 + n) * n) / 2
}

console.time("快方法")
const fastResult = sumFast(1000000000)
console.timeEnd("快方法")

console.log("答案：" + fastResult)

运行，这次快方法几乎是瞬间就给出了答案：

快方法: 0ms
答案：500000000500000000

看到了吗？

  • 慢方法：等了 1 秒多，答案 500000000067109000 —— 是错的
  • 快方法：瞬间完成，答案 500000000500000000 —— 完全正确

这是为什么？

小发现：慢的不仅是时间，连答案都不太准 ​

你一定想问：计算机那么厉害，怎么会算错加法？

因为计算机存大数的时候，用的是近似值（科学家们叫它"浮点数"，就像小数一样， 只能存有限几位）。慢方法做了 10 亿次加法，每一次都有一点点小小的舍入误差， 10 亿次下来，误差越攒越多，最后就差了几亿。

而快方法只做一步运算，误差根本没有机会攒起来，所以答案完全正确。

这个发现很重要：慢方法慢，是有代价的——慢的算法不仅浪费时间，连结果都不可靠。 以后你还会遇到"数字太大存不下"的问题，到时候我们会有专门的办法对付它 （现在先记住一句话：大数要用专门的方法存）。

好，现在回到正题——同样是算到 10 亿，为什么慢方法要 1 秒，快方法却连 1 毫秒都不用？

引出知识点：步数，就是时间 ​

计算机干活，一步就是一步。关键不是"它快不快"，而是它要做多少步。

  • 慢方法：为了加到 10 亿，循环要跑 10 亿次，做 10 亿步加法。 每多一个数，就多一步。有 n 个数，就要做 n 步。 我们把这种"步数和数据量成正比"的速度，叫做 O(n)。 读作"哦——恩"，意思是：数据多一倍，时间也多一倍。
  • 快方法：不管 n 是 100、10 亿、还是 1 万亿，都只用一步公式。 一步就够，永远不变。我们把这种"不管数据多少，都是固定几步"的速度， 叫做 O(1)。读作"哦——一"，意思是：永远一步到位。

现在，把 n 改大 10 倍再试：把 sumSlow(1000000000) 改成 sumSlow(10000000000)（100 亿）。

你会发现慢方法要等更久——大约 10 倍的时间。这就是 O(n)：数据翻 10 倍，时间翻 10 倍。

但快方法依然瞬间完成。不管数据有多大，O(1) 永远是 O(1)。

计算机科学家喜欢把"步数"叫做时间复杂度，用"大 O 记号"来写。 这个 O，就是英文 Order（数量级）的意思——我们只关心"大概多少步"，不关心具体数字。

还有一个量级：猜数字游戏 ​

现在我们玩一个游戏。我写一个程序，它心里想一个 1 到 1000 之间的数，你来猜。

笨办法是从 1 开始挨个猜：1？2？3？……如果答案是 1000，你要猜 1000 次。 1000 步，这是 O(n)。

聪明办法是这么问的：

"比 500 大吗？" —— 如果答案是"是"，你立刻排除了 1~500 这整整一半的数！

再问："比 750 大吗？"——又排除一半。每问一次，剩下的数就少一半。

1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1

数一数：最多猜 10 次，就一定能猜中（因为 2 的 10 次方是 1024，刚好超过 1000）。

猜 100 万以内的数呢？也只要 20 次（2 的 20 次方约是 104 万）！

数据从 1000 涨到 100 万，涨了 1000 倍，猜的次数却只从 10 涨到 20。

这种"每走一步，剩下的问题就减半"的速度，叫做 O(log n)。 log 就是"对数"——你可以把它想成：一个数能被"除以 2"多少次。 1000 能被除以 2 十次左右，所以猜 1000 以内的数只要 10 步。

把代码写出来：

ts
// 猜数字：1 到 1000 之间，程序想了一个数，用二分法找它
function guessNumber(max: number, target: number): number {
  let low = 1
  let high = max
  let steps = 0

  while (low <= high) {
    steps++
    const mid = Math.floor((low + high) / 2)  // 猜正中间
    if (mid === target) {
      return steps   // 猜中了！返回用了多少步
    } else if (mid < target) {
      low = mid + 1  // 目标在右半边
    } else {
      high = mid - 1 // 目标在左半边
    }
  }
  return steps
}

console.log("猜 1000 以内的数，最多用 " + guessNumber(1000, 1000) + " 步")
console.log("猜 1000000 以内的数，最多用 " + guessNumber(1000000, 1000000) + " 步")
console.log("猜 1000000000 以内的数，最多用 " + guessNumber(1000000000, 1000000000) + " 步")

输出：

猜 1000 以内的数，最多用 10 步
猜 1000000 以内的数，最多用 20 步
猜 1000000000 以内的数，最多用 30 步

看到了吗？数据涨了 100 万倍，步数只涨了 20 步。这就是 O(log n) 的魔力—— 数据再大，它也只慢一点点。

今天的三个量级 ​

记号名字含义例子
O(1)常数时间永远固定几步高斯求和公式
O(log n)对数时间每步排除一半二分猜数字
O(n)线性时间数据多一倍，时间多一倍循环累加

以后学到更多算法，你会见到更慢的 O(n²)、O(2ⁿ)。 不过今天，认识这三个就够用了——写程序之前，先想想：我的办法是多少步？

小挑战 ​

  1. 找东西：你的房间里有 100 个玩具，妈妈让你找一个红色的小汽车。 你从门口开始一个个翻，是 O(n) 还是 O(1)？如果玩具柜的抽屉上贴着 "1~10 号在这里"这样的标签，你会怎么找？那又是什么量级？
  2. 加加油：把猜数字的 max 改成 1000000000000（1 万亿），运行看看， 最多要几步？和你猜的一样吗？

课后练习 ​

第 1 题（动手题）：测量速度 ​

把慢方法的 n 依次改成 10、100000、1000000000，运行三次， 把 console.timeEnd 显示的毫秒数记下来。

参考答案（点开查看）

数据变大，耗时明显变长。10 亿的耗时大约是 10 万的一万倍——这正是 O(n) 的特征： n 大多少倍，时间就长多少倍。

（实际测量值取决于电脑快慢，但"越来越慢"的趋势一定一样。）

第 2 题（思考题）：两步还是十步 ​

妈妈让你数清楚书架上有多少本书。方案 A：一本一本数。 方案 B：先数一层有多少本，再数有几层，然后相乘。 这两个方案分别是什么量级？

参考答案（点开查看）

方案 A 是 O(n)：每本书都要数一次，书越多，时间越长。

方案 B 是 O(1)：不管书架上有多少书，都只需要"数一层"+"数层数"+乘法这三步， 工作量不会随书的数量变化。

第 3 题（思考题）：陷阱 ​

下面这段代码，看起来只循环了一层，但它真的是 O(n) 吗？

ts
function count(n: number): number {
  let sum = 0
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      sum++
    }
  }
  return sum
}
参考答案（点开查看）

不是。这是两层循环套在一起：外层每走一步，内层就要走 n 步。 一共是 n × n = n² 步，它的量级是 O(n²)。

O(n²) 的意思是：数据翻 10 倍，时间翻 100 倍。下次学到排序算法时，你会再见到它。

下一课预告：我们要给 50 个同学做点名器。可是……把 50 个名字塞进 50 个变量里， 这真的可行吗？