01先读懂这个概念
先决定 n 和基本操作是什么
如果输入是一个数组，通常令 n 为数组长度。对求和循环，可以数加法次数；对查找，可以数元素比较次数。换电脑会改变一次操作耗时，却不改变这些次数随 n 增长的关系。
n=4 时，扫一遍数组做 4 次工作；扫两遍做 8 次。它们分别是 n 和 2n，增长阶都为 O(n)。这里用 O 表示渐近上界；更精确地说，这两个次数都属于 Θ(n)。省略常数是比较增长趋势，并不是说 4 毫秒和 8 毫秒一样快。
嵌套循环要看执行范围
枚举不同下标的无序二元组，可以令 i 从 0 到 n−1，j 从 i+1 到 n−1。n=4 时，i=0 对应 3 次，i=1 对应 2 次，i=2 对应 1 次，合计 6 次。一般为 (n−1)+…+1 = n(n−1)/2，是二次增长。
两层循环并不总是 O(n²)。如果内层指针在整个算法里只向右走、从不重置，总移动次数可能只有 n；如果候选数量每次减半，执行 k 次后剩 n/2^k 个，令它降到 1，得到 k≈log₂n。后面的窗口和二分会分别用到这两种计数方法。
02从具体数据开始手算
拿一个小输入，逐步手算
枚举 n=4 个位置中的所有 i<j 配对。
| i | j 的取值 | 这一轮次数 | 累计 |
|---|---|---|---|
| 0 | 1, 2, 3 | 3 | 3 |
| 1 | 2, 3 | 2 | 5 |
| 2 | 3 | 1 | 6 |
| 3 | 无 | 0 | 6 |
| 推广 | 每对位置只枚举一次 | n(n−1)/2 | O(n²) |
n 从 4 增大到 8，配对从 6 变成 28；大规模时 n 翻倍，二次项约变成 4 倍。不能用很小的样本要求精确四倍。
03把正确性的理由说清楚
一个可重复使用的分析顺序
- 说清输入规模和统计操作；图算法常需同时使用 V 与 E，不能只写一个含糊的 n。
- 顺序代码累加工作量，独立嵌套按各层执行次数求和；存在共享指针时，统计其全程移动次数。
- 化简表达式，并声明分析的是最坏、期望还是摊还情况。最后单独清点同时存活的额外数据。
04把刚才的思路写成代码
基础课用 Python 表达，先对照变量含义与执行顺序。后续算法课提供 Python、C++ 与 JavaScript 三种实现。
def count_pairs(n):
count = 0
for i in range(n):
for j in range(i + 1, n):
count += 1
return count代码里的每个关键决定
for i in range(n):- 外层执行 n 轮，但不能就此写 n²，因为内层每轮的范围不同。
range(i + 1, n)- 固定 i 时有 n−i−1 个 j，排除了自己以及之前已经枚举的反向配对。
count += 1- 这才是被统计的基本操作。它一共执行 n(n−1)/2 次；函数没有保存每个配对，所以辅助空间仍然是常数。
05这些操作要付出多少代价
把工作量具体数出来
上述代码：次数 T(n)=n(n−1)/2，时间 O(n²)，辅助空间 O(1)。若把每个配对 append 到结果列表，结果存储会变成 O(n²)。
依次执行 O(n) 和 O(n²) 的两段，合计 O(n+n²)=O(n²)。处理两个独立长度 n、m 的输入，最好保留 O(n+m)，不要擅自把 m 当作 n。
递归不是免费空间。若同一时刻挂起 n 个调用，每个保存常数个变量，调用栈为 O(n)。这里先采用定长数值操作模型；任意精度整数、长字符串的比较或哈希还要考虑它们的长度。
06用一个反例检查理解
一次操作可能藏着一次遍历
写 a.copy() 只有一行，却需要复制 n 个引用；排序调用也不会因为写成一个函数名就变成 O(1)。
怎样修正：把库函数的成本计入总工作量。先分析它必须处理多少数据，再考虑语言实现与实际测量。
07自己推一次，再做自测
比较两个方案
方案 A 每次查询都扫描 n 个元素，共 q 次。方案 B 先用 O(n) 建一个索引，再用平均 O(1) 回答每次查询。两者时间和空间有什么区别？
需要一点提示
预处理只付一次；查询付 q 次。
查看完整推导与答案
- A 总时间 O(qn)，若只用循环变量，辅助空间 O(1)。
- B 预处理与查询相加，是期望 O(n+q)，索引空间通常 O(n)。
- 当 q 很小时预处理未必划算；复杂度不直接给出小输入下的真实运行时间。