量快慢的尺子

数一数次数

用秒量会糊涂。
快电脑上，
慢法子也显得快。
所以不用秒，
数“干几次”。
格子有 n 个时，
每种法子
干的次数都不一样。

选个输入大小，数数每种法子干几次。(一个个 = n 次 · 一半一半 = 没几次)

格子少时，
两个看着差不多。
8 格的话，
一个个 8 次，
一半一半 3 次。
没多大差。
可把格子一下子加大，
会怎样呢?

变大了会怎样

这儿真相就露了。
把 n 加大，
有的法子
随格子慢慢长，
有的法子，
格子翻一倍，
活儿就跳到四倍。
n 乘 n，
那就是 n²。

点一点把 n 加大。n 随格子长，可 n² 越到后面长得越像爆炸。

n² 可怕，
是在格子大的时候。
100 格，
n 是 100，
n² 是 10000。
1000 格，
n 是 1000，
n² 是一百万。
开头小，
转眼就大得没法收拾。

比一比曲线

把三种长法
并在一起，
一眼就看出来。
log n，
格子再大
也几乎不往上走。
n 斜斜地直上，
n² 往上一拐，
直冲到老高。

点一点把曲线打开来比。同一个 n 上，log n、n、n² 的高度完全不同。

现在懂了吧。
一半一半地切
为啥那么快。
一半一半是 log n，
格子一千个
十次也就完了。
一个个是 n，
一千就一千次。
长起来的样子，
定了输赢。

只留最大那项

把真实次数数出来，
像 3n²+5n+9，
式子很乱。
可 n 一旦很大，
n² 就把别的
全压下去。
所以把小项擦掉，
只留长得最快的
n²。

点小项，一项项擦掉。3n²+5n+9 里 n 一大就只剩 n²，那就是大O(O)。

前面的数也擦掉。
3n² 也好 100n² 也好，
长起来的样子都是 n²。
所以就写成
O(n²)。
大O 是张名牌，
一行写下
“在大格子里，照什么样子长”。

走到这儿了

总起来是这样。
快慢不拿秒量，
而看长起来的样子。
格子 n 一变大，
log n 几乎不长，
n 随格子长，
n² 会爆。
式子再乱，
只看最大那一项就行，
那个记号就是大O。

点这三个，一行理清。log n 几乎平，n 斜着走，n² 往上爆。只看最大那项就行。

现在看一个法子，
不用掐秒
也能估出快不快。
格子翻倍时
活儿翻倍，还行；
跳到四倍，就当心。
好法子，
是面对大活儿
也长得慢的那种。