什么是大O表示法

不数秒，数次数

用秒来量容易糊涂，因为在快电脑上，慢方法也显得很快。
所以不数秒，而是数“要干多少次活”。
有 n 个格子时，每种方法干活的次数都不一样。

选一个输入大小，看看每种方法要干几次活。（一个个 = n 次 · 一半一半 = 少得多）

格子少的时候，两种方法看起来差不多。
8 个格子，一个个要 8 次，一半一半只要 3 次，差得不多。
可要是把格子一下子加多，会怎样呢？

变大以后会怎样

真正的差别就在这里露出来。
把 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² 向上爆。只看最大的那项就够了。

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