复杂度：数步骤，不背表格.

开篇立了三个问题，第三个——代价花在哪——需要一个记账单位。市面上的教法是发一张表：数组查找 O(n)、哈希 O(1)、快排 O(n log n)，背下来。这个系列不发表格。Big O 是数出来的：盯着代码，数它在格子上走了几步，步数怎么随规模长大。会数之后，任何没见过的结构你都能自己出报价。

—一步是什么.

先定义单位：看一眼算一步——一次比较、一次读写、一次指针跳跃，都记一步。系数先不管（这笔账最后会算）。拿最老实的操作开刀：在一串数里找 23。

func find(list []int, target int) int {
    for i, v := range list { // 每个元素看一眼：至多 n 步
        if v == target {
            return i
        }
    }
    return -1
}

步数至多 n，就记 O(n)：n 翻倍，步数跟着翻倍。O 记号丢掉系数和零头，只留「随 n 长大的形状」——因为 n 一大，形状碾压一切系数。

—三种形状，数三次.

绝大多数代码的步数，逃不出三种数法：

一层循环，n 步。 上面的查找就是。再来一层嵌套，每个元素都要和所有元素见一面：

for i := range list {          // n 次
    for j := range list {      // 每次再来 n 次
        _ = list[i] + list[j]  // 共 n × n 步
    }
}

n 个元素走 n² 步——O(n²)。n 翻十倍，步数翻百倍，这个形状在曲线图上会直接冲出天花板。

每步砍半，log n 步。 有些代码每走一步，就把剩下的问题砍掉一半：

steps := 0
for n := len(list); n > 1; n /= 2 { // 每步问题减半
    steps++                          // 2¹⁰ ≈ 1000：一千个元素只要 10 步
}

从 n 砍到 1 要几步？就是「2 自乘几次到 n」——O(log n)。一百万个元素，20 步。这条曲线后面会反复出场：二分查找靠它，树的高度靠它，堆的上浮下沉也靠它。

形状不用背，可以拖着看。下面的滑杆控制 n，虚线游标带着五个点在曲线上走，台账里是每种形状此刻的真实步数——点哪一行，哪条曲线就拿走唯一的橙色：

—丢系数，丢小头.

数出来的步数常常带着零碎，O 记号只留形状，靠两条删减规则：

丢系数。 连着扫两遍就是 2n 步——但 n 翻倍时它还是跟着翻倍，形状没变：

for _, v := range list { _ = v } // n 步
for _, v := range list { _ = v } // 又 n 步：共 2n，仍记 O(n)

丢小头。 步数是几项相加时，只留长得最快的那项——n 一大，小头连零头都算不上：

// n² + n 步：n=1000 时，后面的 n 只占千分之一
// 记 O(n²)，小头丢掉

不同输入不共用字母。 两个规模无关的输入，各记各的——O(n + m) 不能偷懒合并成 O(n)，因为没人保证 m 比 n 小。

—最坏、平均、摊还.

「至多 n 步」说的是最坏情况——这是默认口径，因为它是能签字的承诺。另外两个口径，各有用处：

最坏

运气最差时走几步。工程默认按它报价：承诺要按兜底写。

平均

所有运气摊平后走几步。查找平均只走一半，但报价仍是 O(n)——形状没变。

摊还

连续做 n 次，总步数摊到每次头上算几步。有些操作偶尔很贵、多数时候极便宜，摊完依然是 O(1)——切片的 append 和哈希表的扩容都靠这笔账做人，到那两篇会把账本摊开。

—空间也一样数.

时间数操作，空间数额外占的格子，同一套形状语言。原地交换两个元素，多用一格临时变量——O(1)；把数组复制一份再排——O(n)。有一种空间开销最容易被漏数：递归每深一层就压一个栈帧，那也是格子——这笔账到递归篇摊开。

—Big O 不等于快.

最后把丑话说在前面：O 记号丢掉的系数和常数，在真实机器上是要还的。三条现实，后面各有一篇兑现：

• —n 很小时，形状还没开始碾压，系数说了算——排序篇里你会看到，几十个元素的小数组上 O(n²) 的插入排序打赢 O(n log n) 的快排，标准库因此把它们混着用。
• —同为 O(n)，连续内存和指针跳跃不是一个速度——cache 的账，数组篇算。
• —所以这个系列的裁决顺序是：先数步骤定形状，再跑测量定输赢。形状告诉你能不能扛住规模，测量告诉你今天谁更快。

最后留一张速查表当索引——注意是索引，不是理解的替代品；会数之后，这张表你自己就能推出来：

记账单位到手。下一篇进第一格内存：指针与结构体——地址就是数据。