从一摞电话本里找一个人——你可以从第一页翻到最后一页，也可以二分定位。前者翻完一千页，后者最多翻十页。这就是效率。

前面我们说效率问题很重要。这一页直接上数字：在一百万条数据里找一个东西，线性扫描要查 100 万次，二分查找只要 20 次。

上一页我们看到线性搜索是 O(n)，二分搜索是 O(log n)。这个 'O' 究竟代表什么？为什么我们只关心它而不关心具体数字？

先看上方的 c·g(n) 与下方的 f(n)，再看 n₀ 之后谁压制谁。

数学定义：∀n ≥ n₀，0 ≤ f(n) ≤ c·g(n)，附日常语言翻译

Big-O 画了天花板——算法不会比这更慢。但最少要花多少？天花板下面，地板在哪里？这就是 Big-Ω 和 Big-Θ 要回答的问题。

上一页我们认识了 O、Ω、Θ 三个记号。但第一次写 f(n)=O(n) 时，很多人会犹豫：这个等号真的能用吗？它其实是个伪装成等号的「属于」关系，许多细节都藏在里面。

从左到右代价越来越大：绿色放心、黄色工程常态、红色小心、黑色基本不可用。

从搜索对比那页我们看到：有些操作几乎不随数据量变化，有些每翻倍只多一步。这两种增长方式就是 O(1) 和 O(log n)。

上页 O(log n) 每次砍半极快，但现实中很多事不能只砍半。比如全班点名必须每个人都叫到；归并排序又得反复拆合。今天看两种典型节奏：O(n) 与 O(n log n)。

对数、线性、线性对数都还「友好」——n 涨 10 倍，计算量涨 10 倍以内。但从平方开始曲线变陡；到了指数，直接「爆炸」。看 O(n²) 和 O(2ⁿ)，找到可接受到不可行的边界。

O(2^n) 已经够恐怖，O(n!) 还要再上一个量级——这是旅行商问题在 n>20 时彻底崩溃的根源。

从一段单层 for 循环开始，逐步推出它的时间复杂度。

从循环执行次数出发，依次分析乘法规律、对数陷阱与边界条件。

归并排序的递归结构与递归树追踪：T(n) = 2T(n/2) + n，每层代价如何累加成 n log n

L5-L6 两次递归合起来是 2T(n/2)，L7 的 merge 给本层加上 n 的代价；tree() 把递归树打出来，每层 cost=n，log n 层相加就是 O(n log n)

上一页我们手撕递归树的层级累加，其实有套路。T(n) = aT(n/b) + f(n) 这一族递归，主定理给了一份三档速判表：先算临界函数，再看 f(n) 落在哪边。

• ✓Big-O 是增长的上界，不等于真实运行时间
• ✓复杂度层级间是数量级鸿沟，常数优化无法跨越
• ✓判定核心：找循环嵌套与递归分支的展开结构
• ✓O 是上界、Ω 是下界，Θ 才是紧确等价
• ✓n 小时常数关键，n 大时量级决定一切

先独立思考，再翻看参考答案。三问覆盖回顾、应用、延伸三个层次。