读完这篇，你能做什么
能从代码统计操作数量，并区分渐近增长、单次成本和实际测量。
学习理由、准备要求与知识点
为什么学它
复杂度提供比较方案的共同语言，避免只凭一次计时选择算法或集合。
先读这些内容
知识点清单
- 输入规模与关键操作
- O/Ω/Θ 定义
- 最好平均最坏情况
- 循环次数推导
- 线性平方对数增长
- 额外空间与调用栈
- 摊还成本
- 数据库往返的整体成本
运行前先确认Java 17；源码在本机 Microsoft OpenJDK 17.0.20.1 src.zip 核验，在线链接为上游 jdk-17.0.20-ga。深入模块可在掌握基础后回读。
01先弄懂它是什么
复杂度要回答的是：数据变多以后，程序的工作量会怎样增加。先说明 n 代表什么，比如订单数或字符串长度，再数关键操作。大 O 表示增长的上界，大 Ω 表示下界，大 Θ 表示上下界同阶；这些符号描述增长趋势，不是在某台电脑上必定耗时多少毫秒。
例如，两段各处理 n 项的循环顺序执行，工作量通常相加；每处理一项都再完整扫描 n 项，通常要相乘。但不能看到两层循环就断定是平方增长：若内层指针全程只向前走 n 次，总量仍可能很小。小数据的实际耗时还受内存分配和硬件等影响，要数执行次数，也要用测量检验真实场景。
最好、最坏和期望情况需要说明输入条件或概率假设，摊还分析则研究一串操作的总成本，不是同一种平均。空间复杂度还需说明是否包括输入、输出与递归栈。对任意精度整数、长字符串比较或远程调用，单次操作并不一定常数，不能机械套用只适合固定宽度基本值的模型。
文中这几个词，先认一认
- 输入规模
- 数据有多大，例如元素数、字符数；一个问题也可能需要同时用行数和列数描述。
- 渐近上界
- 例如工作量是
O(n)，意思是数据量 n 超过某个起点后，操作次数不超过 c×n，其中 c 是固定常数。这给的是大规模时的增长上限，不是每次恰好做 n 步，也不是承诺多少毫秒。 - 摊还分析
- 先算连续多次操作一共花多少，再分摊到每一次，允许其中几次较贵。
- 预处理
- 先花一次时间整理数据，例如建索引，以便后续反复查找更快。
02看看它怎么工作
分析从真实执行路径开始。线性查找最坏检查全部 n 项，二分查找依赖已经排序且可快速定位中点，每次排除约一半候选，经过 k 次剩余约 n/2^k 项，因此 k 随 log n 增长。如果排序本身也属于一次性任务，总成本还要包括排序，不能只报告最后查询那一步。
分析递归要分开数两件事：总共做了多少工作，以及同一时刻最多套了多少层调用。两个分别处理一半数据的递归调用，总工作仍可能是线性或线性对数；大量重复求解相同小问题才会明显浪费。把分支数量、每个小问题的规模和合并成本写成递推关系，再推算增长，不能只因为用了递归就判定它慢。
预处理是否值得取决于查询次数。对 n 项数据做 q 次区间求和，逐次扫描最坏 O(nq)；建立前缀和需要 O(n)，每次查询 O(1)，总共 O(n+q)，代价是额外 O(n) 存储和更新不再直接。图把一次构建与重复查询分开，提醒分析必须覆盖整个使用周期。
正在加载流程图…
查看流程图源码（Mermaid）
flowchart TD
A["明确 n 与查询次数 q"] --> B{"是否重复查询同一数据"}
B -->|"少量"| C["直接扫描：每次按区间长度"]
B -->|"大量且数据固定"| D["一次 O(n) 建前缀和"]
D --> E["每次用两次索引与一次减法"]
E --> F["总成本 O(n+q)，额外 O(n) 空间"]
C --> G["累计完整工作量再比较"]
F --> G按顺序看，每一步做了什么
- 定义所有输入规模维度。
- 数出各操作的实际执行次数。
- 说明最好、最坏或期望前提。
- 计算辅助空间与递归栈。
- 把构建、查询、更新和实际测量分开评估。
03对照实现代码
Microsoft OpenJDK 17.0.20.1；java.base/java/util/Arrays.java · java.util.Arrays#binarySearch0(int[],int,int,int)
以下为原创 Java 17 教学实现，不是原样 JDK 源码；只保留文中明确讨论的机制，省略优化、兼容及内部接口。
public final class SourceModel {
public static int search(int[] sorted, int target) {
int low = 0, high = sorted.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int value = sorted[mid];
if (value == target) return mid;
// 每个失败比较都排除中点及不可能的一半。
if (value < target) low = mid + 1;
else high = mid - 1;
}
return -(low + 1); // 负值编码插入位置，保留零位置可表示性。
}
}真实 int 数组 binarySearch0 维护 low 与 high，通过中点值比较更新一侧边界，找到就返回，未找到返回负的插入位置编码。模型改用等价的中点计算写法，只处理整个数组并假定已排序；不模拟公开方法的范围校验和其它类型重载。
循环次数的关键不是每轮有多少行，而是候选区间如何缩小。未命中时至少排除中点及一侧不可能范围，剩余数量约减半；从 n 到一需要对数级轮数。数组索引和 int 比较采用常数成本模型，所以这段循环的最坏查找时间为 O(log n)。
二分查找的前提是数据按相同规则排好序，否则没有理由排除其中一半；有重复值时也不保证找到第一项。若每次查询前检查排序，就要额外做 O(n) 工作；若要最左位置，还需改写每轮保留的范围和停止条件。阅读 API 时要分清哪些前提由调用方保证。
实现返回插入位置的负编码，说明结果解释也是接口成本的一部分。调用者必须区分非负命中与负值未命中，不能直接把负值当数组下标。源码分析提供算法证据，但不能据此宣布某次实际业务请求延迟等于对数，因为读取、分配和外部 IO 可能占据主要时间。
代码先调用谁，再调用谁
- 公开
binarySearch接口建立范围前提 binarySearch0初始化候选闭区间- 比较中点并排除不可能一侧
- 返回命中下标或插入位置编码
04动手写一个例子
预处理前缀和实现重复区间求和
对固定 int 数组建立前缀和，查询左闭右开区间 [lo,hi) 的 long 总和。允许空数组和空区间，拒绝 null 与非法范围；构建后不受原数组修改影响。
- 输入 1
数组[2,-1,4]，查询[1,3)- 输出 1
3
- 输入 2
查询[0,3)- 输出 2
5
- 输入 3
查询[2,2)- 输出 3
0
建立长度 n+1 的前缀数组，让 prefix[0] 等于零，prefix[i+1] 等于前 i+1 项之和。额外的零位置让从数组起点开始的区间无需特殊分支，也让空区间自然得到零。每个输入元素只用于一次累积，构建成本线性。
区间 [lo,hi) 的和等于前 hi 项的和减去前 lo 项的和，共同前缀被抵消。这一恒等式依赖加法可逆，不意味着任何聚合都能用相减恢复，例如区间最大值不能通过两个前缀最大值相减得到。适用运算性质是数据结构选择的一部分。
返回 long 防止常见 int 总和溢出；对 Java int 数组的可表示长度与元素范围，整体和及任意区间和落在 long 范围内。构建后只保存累计数值，不保存原数组引用，因而原数组修改不会自动更新查询结果。它是固定快照，频繁更新时应选择不同结构。
为什么这样写是对的构建到位置 i 后，prefix[i] 精确等于原数组前 i 个元素之和。
构建遍历 n 次；每次查询仅做固定边界检查、两次数组读取和一次减法，不扫描区间长度。
保存为 Main.java，运行 javac --release 17 -encoding UTF-8 Main.java，再运行 java Main。程序包含固定输入自测，断言失败时会抛出错误。
展开收起代码 · Main.java · 完整可运行程序
长行可在代码区域内左右滚动，按 Tab 可把焦点移入代码区。
public class Main {
static final class RangeSums {
private final long[] prefix;
RangeSums(int[] values) {
if (values == null) throw new IllegalArgumentException("values");
prefix = new long[Math.addExact(values.length,1)];
// 多一个零前缀位置，让起点和空区间统一处理。
for (int i = 0; i < values.length; i++)
prefix[i+1] = prefix[i] + values[i];
}
long sum(int lo, int hi) {
if (lo < 0 || hi < lo || hi >= prefix.length)
throw new IllegalArgumentException("range");
return prefix[hi] - prefix[lo]; // 抵消共同前缀。
}
}
static void require(boolean condition) {
if (!condition) throw new AssertionError();
}
public static void main(String[] args) {
int[] input = {2,-1,4};
RangeSums sums = new RangeSums(input);
// 完整、部分、空区间和空输入各有确定结果。
require(sums.sum(0,3) == 5);
require(sums.sum(1,3) == 3);
require(sums.sum(2,2) == 0);
require(new RangeSums(new int[0]).sum(0,0) == 0);
require(new RangeSums(new int[]{Integer.MAX_VALUE,Integer.MAX_VALUE})
.sum(0,2) == 4294967294L);
input[0] = 99; // 构建结果是数值快照，不保留可变输入引用。
require(sums.sum(0,3) == 5);
boolean rejected = false;
try { sums.sum(2,1); } catch (IllegalArgumentException e) { rejected = true; }
require(rejected);
System.out.println("PASS 7");
}
}这些特殊情况也要试一试
- 空区间返回加法单位元零。
- 空数组仍有一个零前缀位置。
- 负数元素不破坏前缀差恒等式。
- 原数组后续修改不会更新快照。
进阶选读 · 可选深入：频繁更新的区间查询
场景数据不断发生单点修改，仍需大量区间和。
做法Fenwick 树或线段树把更新与查询都组织为对数级路径，明确下标约定并保留单位元；根据更新形态再考虑懒标记。
复杂度常见单点更新与区间和各 O(log n)，存储 O(n)。
好处与代价实现复杂度高于前缀和；只读数据不必为并不存在的更新能力付出维护成本。
05项目里怎么用
复杂度能先排除数据增多后工作量涨得太快的方案，实际提速仍需测量。小型性能实验要考虑热身、编译器优化、输入分布，以及结果是否真正被使用；业务测试则看完整请求耗时、吞吐和资源。小数据某次跑得快，不代表大规模增长更好，一次测量也不代表稳定表现。
把外部调用放进循环时，时间成本往往由网络或数据库决定，而不是本地几次比较。批量请求、索引和缓存可能改变调用次数，但同时带来一致性、内存和失效管理。复杂度表达式可以把调用成本写成变量，帮助团队看清真正值得优化的部分。
资源分析应包含输出规模和失败路径。一个理论上快速的算法若必须输出百万项，仍需要相应时间与内存；递归、临时数组和缓存也会占空间。对不可信输入应设合理上限，给出清晰拒绝或分页策略，而不是仅在文档写 O(n) 就认为任何 n 都可接受。
容易踩的坑
- 只看到嵌套循环就判定平方复杂度。
- 把摊还与概率平均混为一谈。
- 忽略排序、索引建立和输出成本。
- 把大 O 当成具体毫秒数或质量排名。
几种做法，怎么选
表格有四列，窄屏可左右滑动查看代价和适用条件。
| 方案 | 优势 | 代价与限制 | 适用条件 |
|---|---|---|---|
| 直接扫描 | 实现简单且无额外索引 | 重复查询成本高 | 查询少或数据频繁整体变化 |
| 前缀和预处理 | 固定数据查询常数时间 | 更新后需重建或维护 | 大量只读区间和 |
| 动态树结构 | 兼顾更新和查询 | 实现与常数成本更高 | 频繁局部更新并查询 |
06检验是否读懂了
先自己想、自己写，再展开答案核对。场景题是假设的练习情境；遇到还没学过的内容，可以做完基础后再回来。
先用自己的话解释
01O(n) 是否意味着一定比 O(n log n) 快？
展开参考答案与推导
不在所有有限规模上成立。常数、输入分布和实现质量会影响实际时间；渐近分析说明增长趋势，仍需结合数据规模和测量，不能把符号直接当作毫秒比较。
02两个指针的嵌套循环为何可能线性？
展开参考答案与推导
如果两个指针都只向前且各最多推进 n 次，总推进次数受线性界限制。应数整个执行过程的总动作，不能把语法嵌套层数机械相乘。
03前缀和为什么需要 n+1 个位置？
展开参考答案与推导
prefix[0] 表示零项之和，prefix[i] 表示前 i 项。这样区间和统一写成 prefix[hi]-prefix[lo]，从零开始和空区间无需额外分支，边界也容易证明。
换个情况，还会处理吗
01二分查询很快但整个功能仍慢，可能漏算什么？
展开参考答案与推导
可能每次查询前都重新排序、读取远程数据或复制大数组。应计算完整生命周期成本，并判断排序和索引能否复用，不能只报告内部二分循环的复杂度。
02前缀和查到旧值，是线程问题吗？
展开参考答案与推导
先确认结构是否定义为固定快照。原数组修改不会自动更新累计值，这是当前接口语义；需要动态更新时应重建或选择更新结构，再讨论并发同步。
03大整数算法写 O(n)，还应补什么前提？
展开参考答案与推导
说明 n 表示元素数还是数位数，并计入加乘除的数位成本。任意精度操作不是固定宽度机器指令，忽略值长度可能严重低估时间与空间。
写代码试一试
01验证负数区间
- 输入 / 条件
[-3,2,-1] 查询[1,3)- 输出 / 预期
1
提示 前缀可下降。
展开参考答案与推导
建立该数组并断言结果为一。前缀和不要求单调，减去共同前缀仍成立；不能把前缀数组必须递增当成此算法的前提。
02给查询统计操作次数
- 输入 / 条件
任意长度区间- 输出 / 预期
固定两次数组读取
提示 只统计定义好的基本操作。
展开参考答案与推导
在教学版本中为两次 prefix 读取分别计数，比较短区间与长区间次数相同。这个计数说明算法结构，不是测得 CPU 指令数，也不包括边界检查等未定义计费项目。
03为什么不能用前缀最大值做相减查询？
- 输入 / 条件
[5,1,2] 查询[1,3)- 输出 / 预期
最大值2
提示 最大运算不可通过相减撤销。
展开参考答案与推导
前缀最大值在多个位置都为五，无法恢复后两项最大值二。需要稀疏表或线段树等适合最大聚合的结构，选择数据结构必须依据运算性质而非照搬求和公式。
读完之后，独立完成
课后作业：自己做一遍
本篇共 10 道作业，先完成 8 道基础与综合任务，再按前置知识挑战进阶题。其中包含 1 道思维拓展，试着换个条件，看看原来的办法是否还管用。不附参考答案。
能从代码统计操作数量，并区分渐近增长、单次成本和实际测量。
本篇重点加练
重点加练成本模型与摊还分析，要求解释输入规模和累计操作而不只背公式。
- 输入规模与关键操作
- 摊还成本
重点内容会多练几次。先说清楚怎么做，再试试空数据、出错或条件改变时会发生什么。
先自己做，卡住时记下问题，再回来查。问答题写清“为什么、什么时候适用”；动手题留下输入、输出和运行步骤，方便下次重做。
基础必做
- 作业 01原理问答
以线性查找为例分别定义输入规模和关键操作，写出上界、下界与紧确界陈述；每个陈述注明适用的输入集合和常数前提。
- 提交内容
- 符号定义、操作计数及三类界的表述。
- 怎样算完成
- 复杂度符号含义准确
- 不把 O 当作实际毫秒数
练到的知识点输入规模与关键操作 · O/Ω/Θ 定义
- 作业 02代码推演
分析在数组中找首个目标的循环，输入长度 n，目标分别位于首项、末项及不存在；再明确一种随机输入分布推导平均比较次数。
- 提交内容
- 三类计数与平均情形前提。
- 怎样算完成
- 最好最坏平均分开
- 平均结果依赖明确概率模型
练到的知识点最好平均最坏情况 · 循环次数推导
- 作业 03原理问答
字符串查找算法用 n 表示记录数，却忽略每条字符串长度。为该任务重新定义输入规模和关键操作，给出不同长度分布的成本表达。
- 提交内容
- 输入模型、计数项和比较样本。
- 怎样算完成
- 参数含义明确
- 比较成本与记录数量分开
练到的知识点输入规模与关键操作
综合应用
- 作业 04编程实践
实现线性遍历、双重配对与有序二分三个小程序，加入操作计数，在 n=16、32、64 运行；同时记录额外数组和递归深度。
- 提交内容
- Java 程序、自写结果测试、计数表及运行证据。
- 怎样算完成
- 比较工作量而非只看耗时
- 空间计算不遗漏调用栈
- 二分输入有序性被保证
练到的知识点线性平方对数增长 · 额外空间与调用栈
- 作业 05原理问答
设计动态数组连续追加的成本账本，给出一次昂贵扩容与一段连续操作的不同计量方式；说明摊还结论需要怎样的容量增长政策。
- 提交内容
- 容量序列、累计成本推导与前提。
- 怎样算完成
- 单次和累计成本分开
- 增长策略改变后的边界明确
练到的知识点摊还成本
- 作业 06面试场景
接口在内存里用
O(n)算法处理一百条记录，但逐条查询数据库，另一个实现增加排序却只发一次查询。制定端到端成本模型和公平测量计划。- 提交内容
- 计算/分配/往返成本表与实验计划。
- 怎样算完成
- 远程等待纳入总成本
- 不只按本地 Big-O 排优劣
练到的知识点输入规模与关键操作 · 线性平方对数增长 · 数据库往返的整体成本
- 作业 07编程实践
实现一个可选固定增量或成倍扩容的整数容器模型，只计数搬移量不追求库级性能；对同样的追加序列记录每次和累计成本。
- 提交内容
- Java 模型、自写内容/容量边界测试与计数证据。
- 怎样算完成
- 两策略处理相同输入
- 分配次数和搬移量分别计量
练到的知识点输入规模与关键操作 · 摊还成本
- 作业 08代码推演
某缓存平时插入常数步骤，每累计 k 次插入执行一次清理。用符号表示连续 n 次操作的总量，区分 k 固定与随 n 增长两种政策。
- 提交内容
- 累计成本账本和前提说明。
- 怎样算完成
- 昂贵操作次数被明确计算
- 结论注明参数关系
练到的知识点摊还成本
进阶挑战 · 掌握前置后选做
- 作业 09编程实践
完成数组后：为重复区间求和实现扫描与预处理两个版本，输入含负数和空区间；给定不同查询次数比较总成本，并用独立参考核对。
- 提交内容
- Java 实现、自写边界测试、总成本推导及运行证据。
- 怎样算完成
- 预处理成本计入
- 时间空间权衡与查询量相关
- 数值范围政策明确
练到的知识点最好平均最坏情况 · 循环次数推导 · 额外空间与调用栈 · 摊还成本
思维拓展
先写出你的猜想，再用例子或实验验证。答案可以不同，但要说清依据、适用情况，以及还有什么没弄懂。
- 作业 10思维拓展 · 条件变化
系统关心的指标从总吞吐改为每次操作最多 2ms。重新评审摊还成本作为验收依据是否充分，提出还需测量或约束的部分。
- 提交内容
- 吞吐与延迟合同对照及实验设计。
- 怎样算完成
- 单次与累计保证分别陈述
- 结论能对应业务时限
练到的知识点输入规模与关键操作 · 摊还成本
完成后，再检验一次
给每题标记“独立完成 / 查阅后完成 / 尚未完成”。查过资料或没做出的题，记下卡在哪里。隔一天换一组输入再试，能解释结果和出错原因，再把这个知识点标为掌握。
继续阅读
先看能帮你完成当前练习的部分。例子跑通后，再读更深入的解释。
- 必读教程英文
Harvard CS50：算法 （新标签页）↗
阅读线性/二分查找、排序与 O/Ω/Θ，跟随具体输入推导操作次数。
- 实践参考文档英文
Java 17 API：Arrays （新标签页）↗
查阅
copyOf、equals、sort、binarySearch和asList的具体契约。 - 深入参考文档英文
Java 17 API：HashMap （新标签页）↗
阅读散列分布、迭代、fail-fast 与非线程安全前提，区分实现和约定。
- 深入参考文档英文
OpenJDK 17u java.util.Arrays （新标签页）↗
定位
intbinarySearch0的候选区间缩减，推导对数比较次数并保留排序前提。 - 深入参考文档英文
Princeton 算法分析 （新标签页）↗
阅读成本模型、实验分析与数量级推导。