大 O 记号
大 O 记号是一种简洁的速记，用来表示当输入变大时某样东西增长得有多快，写成 O(...)，读作「……的阶」或「大 O 的……」。它是我们说话的语言：「这个算法是线性的」写作 O(n)，「这个是平方级的」写作 O(n^2)，「这个几乎不怎么变慢」写作 O(log n)。最值得养成的一种直觉是：大 O 会忽略细枝末节和常数，只保留当 n 极大时占主导的那一项。想象两辆车。一辆起步快但有极速上限；另一辆永远在加速。短距离冲刺第一辆赢，可道路够长，第二辆总会反超。大 O 关心的就是那条长路——n 无限增大时的行为。
两条简单规则就能让它豁然开朗。第一，丢掉常数因子：3n + 50 就是 O(n)，因为把工作量翻三倍、或加上固定的 50，并不改变曲线的形状，只改变它的陡峭程度，而陡峭程度是个硬件细节。第二，只保留最大的那一项：n^2 + n + 100 是 O(n^2)，因为一旦 n 变大，n^2 那部分就把其余一切都比下去了。所以 O(n^2) 并不意味着「恰好 n^2 步」——它意味着「增长不会快过某个常数乘以 n^2」。它是增长率的一个上界，而不是步数。
一条好用的阶梯，随 n 增大从最仁慈到最残酷：O(1) 常数、O(log n) 对数、O(n) 线性、O(n log n)（好的排序的速度）、O(n^2) 平方、再到 O(2^n) 指数（它会很快变得毫无希望）。别被符号吓住：大 O 不过是一个关于「如何随规模放大」的承诺。它故意把小东西扔掉，好让你能凭两个算法的本质性格去比较它们，挑出那个在输入变大时仍能屹立不倒的。
long long sum = 0; for (int i = 0; i < n; ++i) // loop runs n times sum += a[i]; // O(n) total work, O(1) extra space
把 n 个数求和，做约 n 次加法：O(n) 时间、O(1) 额外空间。
O 是上界（增长不快过）。它的兄弟们：Omega 是下界，Theta 是紧界（上下界同时成立）。日常说话里，「O」通常指最坏情况的增长。