Engineering Review Lab

Appearance

时间与空间复杂度分析导论（Big O 表示法） ​

回到总览：00 基础知识（Foundations）相关模块：树与红黑树基础 · 哈希表原理、HashMap 扩容与哈希冲突解决 · 栈、队列与堆（优先队列）基础与工程应用

一句话定义 ​

复杂度分析是在不依赖具体机器与一次性 benchmark 的前提下，判断算法随输入规模 N 增长时，时间成本和额外空间成本会如何放大的方法；对 Android / Compose / Flutter 工程师来说，它的价值不是做竞赛题，而是提前识别“代码上线后会不会随数据量增长变卡、变耗电、变爆内存”。

代码索引 ​

本主题暂无独立 Lab；本页以内嵌代码示例为主，容器复杂度对照见 栈、队列与堆（优先队列）基础与工程应用，HashMap 与空间换时间见 哈希表原理、HashMap 扩容与哈希冲突解决。

为什么需要 ​

  • 为什么在移动端开发里，即使 O(N) 和 O(N²) 在测试数据 N=10 时运行时间相近，也必须严格拒绝 O(N²) 写法？

    • 一句话答：随着业务数据增长（如本地联系人、消息列表、日志从 N=1_000 增至 N=10_000），O(N²) 的比较/配对次数会从约 100 万步激增至约 1 亿步；若这段逻辑跑在主线程，很容易从“偶尔卡一下”变成秒级卡顿甚至 ANR。复杂度决定的是代码的增长上限，不是一次本地跑分的偶然快慢。

  • 为什么 Android / Compose / Flutter 工程师做优化时总在讲“空间换时间”？

    • 一句话答：绝大多数移动端优化本质上都是“以空间换时间”——HashMap / HashSet 用 O(N) 额外空间换 O(1) 平均查找；LruCache / Bitmap 缓存用内存换重复解码与重复 IO；预计算索引用一份中间结构换掉高频路径里的重复扫描。在物理内存受限的手机上，关键不是“能不能换”，而是“换多少、何时失效、会不会 OOM”。

  • 为什么 Big O 不能替代真实 profiling / trace？

    • 一句话答：Big O 只描述增长阶数，不描述常数、对象分配、GC、布局测量、Compose 重组、Flutter rebuild、锁竞争和 IO。同样是 O(N)，纯数组下标访问和“遍历 + 字符串拼接 + 日志打印 + 创建临时对象”完全不是一回事；工程里要先用复杂度筛掉明显错误的结构，再用 profiler 验证真实热点。

  • 为什么 Compose / Flutter 特别容易把复杂度问题“写得很自然”？

    • 一句话答：声明式 UI 很容易在“状态变化 → 重组 / rebuild”路径里顺手再做一遍 filter / map / sort；数据量小时没感觉，一旦列表上千、输入框每次击键都触发重算，原本 O(N) 或 O(N log N) 的集合运算就会直接变成掉帧源头。

这页解决什么问题 ​

  • 看到循环、递归、查找、排序、缓存、索引时，我怎么快速判断复杂度？

    • 一句话答：先识别代码结构属于“单次扫描、区间减半、双层嵌套、递归分裂、先建索引再查找”中的哪一种，再数最内层核心操作被执行了多少次；详见下文 §快速判断模板 与 §四步法。

  • 为什么两个都叫 O(N) 的方案，线上表现仍可能差很多？

    • 一句话答：因为复杂度只告诉你趋势，不告诉你常数；主线程数组扫描、对象分配、字符串构造、日志打印、Compose 重组、Flutter rebuild、布局测量虽然都可能是 O(N)，但真实成本可能差出数量级。详见下文 §Big O 不替你处理常数。

  • 什么时候该用 HashMap / Set / 缓存 / 堆，什么时候不该用？

    • 一句话答：当你在高频路径里反复扫描同一批数据、或重复读取同一资源时，通常应考虑索引化或缓存；但如果数据很小（如 N < 50）、只跑一次、或内存/失效管理成本过高，就不一定值得换。详见下文 §时间与空间的典型交换 与 §Android / Compose / Flutter 主线理解。

底层机制 ​

1. 先看增长阶，而不是先看毫秒数 ​

复杂度真正回答的是：当数据量扩大 10 倍、100 倍时，这段代码成本会怎样变化。

text
O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N) < O(N!)
text
计算步数
  ^
  │                                    / O(N²)
  │                                  /
  │                                /  / O(N log N)
  │                              /  /
  │                            /  /  / O(N)
  │                          /  /  /
  │                        /  /  /   / O(log N)
  │                      /  /  /   /
  │────────────────────/──/──/───/─────/───── O(1)
  └───────────────────────────────────────────────► 输入规模 N

记忆钩子：数据加一个零，O(N²) 的工作量大约乘一百；O(log N) 则是“免费的午餐”——100 万元素二分查找大约只要 20 步。

2. 把每一档复杂度装进日常动作 ​

复杂度日常比喻增长体感工程直觉
O(1)已知页码直接翻到那页数据再大也几乎一步到位数组下标、Map.get 平均查找
O(log N)猜数字，每次砍一半数据翻倍，只多 1 步左右有序数组二分、平衡树
O(N)从头逐页找一句话数据翻倍，工作量翻倍列表扫描、过滤、求和
O(N log N)分堆整理卡片再归并比线性慢，但仍可控全量排序常见档
O(N²)N 个人两两握手数据 ×10，工作量 ×100双重循环比对、嵌套查找
O(2^N)暴力试所有开关组合每多一个变量，成本翻倍朴素递归、无 memo 回溯

3. 快速判断模板：看到代码结构先归类 ​

面试、代码审查、线上排障时，不要从零推公式，先问“这段代码长得像哪一类”。

模板 A：单次扫描 → 通常 O(N) ​

kotlin
fun countUnread(messages: List<Message>): Int {
    var count = 0
    for (m in messages) {
        if (!m.isRead) count++
    }
    return count
}
  • 判断：一层循环，最内层只做常数次操作 → O(N)。
  • 常见误判：以为“里面还有 if”就会变 O(N²)；if 不增加循环层数，仍是 O(N)。

模板 B：每轮减半 → 通常 O(log N) ​

java
int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = (lo + hi) >>> 1;
    if (a[mid] == target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
  • 判断：每轮搜索区间减半 → 约 log₂ N 轮。
  • 常见误判：数组无序也硬套二分；无序列表线性扫描才是 O(N)。

模板 C：双层都跟输入规模增长 → 通常 O(N²) ​

java
for (String a : listA) {
    for (String b : listB) {
        if (a.equals(b)) return true;
    }
}
  • 判断：外层 N 次 × 内层 M 次 → O(N × M)；若 N ≈ M 就是 O(N²)。
  • 常见误判：内层只是固定 3 次循环时，总体仍是 O(N)，不是 O(N²)。

模板 D：递归分裂且大量重复子问题 → 警惕 O(2^N) ​

java
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
  • 判断：每个调用分裂成 2 个子调用，且子问题大量重复 → 指数级。
  • 常见误判：看到递归就以为是 O(N)；要看分支数和是否重复计算。

模板 E：先建索引再查找 → 常见 O(N + M) ​

java
Set<String> setB = new HashSet<>(listB); // O(M)
for (String a : listA) {
    if (setB.contains(a)) return true;   // O(1) 平均
}
  • 判断：建索引 O(M) + 扫描 O(N) → 总计 O(N + M)，用 O(M) 空间换掉 O(N × M) 时间。
  • 常见误判：以为 HashMap 永远是 O(1)；最坏哈希冲突、扩容、装箱仍要纳入工程判断。

4. 四步法：不会推复杂度时怎么数 ​

复杂度推导不神秘，本质就是数最内层核心操作被执行了多少次。下面四步每一步都配一个可复用例子。

第 1 步：找基本操作 ​

找最内层真正重复执行、且决定成本的操作：

代码片段基本操作
if (list.contains(x))一次相等比较 / 哈希查找
sum += a[i]一次数组访问 + 一次加法
map.get(id)一次哈希计算 + 桶访问
items.filter { ... }每个元素一次谓词判断

第 2 步：数执行次数 ​

结构怎么数例子
单循环跟循环次数同阶for (i in 0 until n) → n 次
嵌套循环外层 × 内层n × n → n²
每轮减半log₂ n 轮二分查找
递归分裂看递归树节点数朴素斐波那契 → 约 2^n 个节点

第 3 步：去掉常数和低阶项 ​

原始表达式记成
2N + 100O(N)
3N² + 5N + 1O(N²)
N log N + NO(N log N)

Big O 忽略常数和低阶项，所以 O(2N) 和 O(N) 同阶；但移动端主线程里“扫 1 遍”和“扫 3 遍”体感仍可能差很多。

第 4 步：看增长趋势 ​

问自己：N 翻 10 倍，工作量大约翻几倍？

若翻约…多半是
几乎不变O(1) 或 O(log N)
10 倍O(N)
10～30 倍O(N log N)
100 倍O(N²)
1024 倍O(2^N)

口述回答模板 ​

“这段代码最内层是 _，外层循环/递归让它一共执行约 _ 次；去掉常数和低阶项后是 O(___)。若 N 从 1_000 涨到 10_000，成本大约会 ___。”

5. 三个完整推导例子 ​

例 1：双重循环 = O(N²) ​

java
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        sum += a[i] * b[j];
    }
}
  • 可能执行顺序
    1. 外层跑 n 次。
    2. 每次外层里，内层再完整跑 n 次。
    3. 最里面的乘加语句一共执行 n × n 次。
  • 可能输出
    text
    基本操作次数 ≈ N²
n=1_000 → 约 1_000_000 次
n=10_000 → 约 100_000_000 次
  • 预期现象
    • 数据量 ×10，执行次数约 ×100。
  • 观察重点
    • 两层循环不一定就是 O(N²)，关键要看每层是否都跟 N 同阶增长。

例 2：二分查找 = O(log N) ​

java
int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = (lo + hi) >>> 1;
    if (a[mid] == target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
return -1;
  • 可能执行顺序
    1. 每轮只看中间元素。
    2. 命不中就把搜索区间直接砍半。
    3. 从 N -> N/2 -> N/4 -> ... -> 1。
  • 可能输出
    text
    1_048_576 个元素，最多比较约 20 次
  • 预期现象
    • 数据从千级涨到百万级，比较次数增长很慢。
  • 观察重点
    • 前提是“数据有序”；无序数据不能硬套二分复杂度。

例 3：朴素递归斐波那契 = O(2^N) ​

java
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
  • 可能执行顺序
    1. fib(n) 分裂成 fib(n-1) 和 fib(n-2)。
    2. 子问题继续分裂。
    3. 大量重复子问题被反复计算。
  • 可能输出
    text
    n=30 时调用次数已达百万级；n=40 时接近千万级
  • 预期现象
    • 这类代码在线上通常不是“慢一点”，而是直接不可用。
  • 观察重点
    • 若出现“递归树大量重复子问题”，通常要想 memoization / DP，而不是继续微调语法。

6. 时间复杂度与空间复杂度怎么一起看 ​

只看时间不够，因为很多优化是“省时间但更吃内存”：

时间与空间的典型交换（移动端工程取舍）

做法时间变化空间变化常见工程例子
双重循环改 HashSetO(N²) → O(N)O(1) → O(N)黑名单判断、去重、交集计算
LruCache / Bitmap 缓存重复解码减少额外缓存对象图片列表、头像、缩略图
预加载配置 / 预分组重复计算减少额外索引结构首页 Tab、分组列表
流式处理 / 分页时间未必更低空间更稳大文件导入、长日志解析
复制快照再 diff逻辑更简单内存翻倍列表快照、UI diff

均摊复杂度：为什么 ArrayList.add() 常说是 O(1) ​

动态数组偶尔会因为扩容做一次 O(N) 拷贝，但不是每次 add 都这么贵：

  • 大多数时候数组还有空位，直接写入，接近 O(1)。
  • 偶尔扩容时，要把旧元素全部拷贝到新数组，这一次是 O(N)。
  • 均摊复杂度不是概率意义上的 average-case，而是对“一整串 add 操作”的总成本做分析：昂贵的扩容必须先经历很多次便宜插入才会再来一次。

工程类比：偶尔一次搬家很贵，但如果你两年才搬一次，把成本摊到每天，平均成本并不高。

7. Big O 不替你处理常数，但主线程非常在意常数 ​

复杂度里 O(N) 和 O(2N) 会被视为同阶，但移动端不能因此忽略常数：

同为 O(N) 的写法为什么体感差很多
int[] 顺序访问连续内存，缓存友好
遍历 + String 拼接大量临时对象，触发分配与 GC
遍历 + 打日志IO 与字符串格式化成本极高
Compose 重组里 filter + sort每次状态变化都重算集合
Flutter build() 里 where().toList()..sort()每次 rebuild 都重算

所以工程决策顺序通常是：

  1. 先用复杂度排除明显错误的结构（如高频路径上的 O(N²)）。
  2. 再看常数、对象分配、GC、重组/rebuild、布局测量、锁竞争。
  3. 最后用真实 profiling / trace 验证热点是否真的命中你的假设。

看到这类问题时怎么回答 ​

这一节直接服务面试、复盘和代码审查中的口头表达。

  • 看到单层循环扫描列表

    • “这是 O(N)，因为每个元素只处理一次。若跑在主线程且 N 上万，需要确认是否高频触发。”

  • 看到嵌套循环或列表项里再线性查找

    • “这是 O(N²) 或 O(N × M)。测试数据小时可能没感觉，但联系人/消息/日志规模上来后会爆。通常应先建 Map / Set 索引。”

  • 看到全量排序但业务只要 Top-K

    • “全量排序至少 O(N log N)。如果只要前 10 条，应考虑堆、PriorityQueue、数据库 LIMIT 或分页，而不是每次全排。”

  • 看到 LruCache / HashMap / 预计算

    • “这是典型的空间换时间：用 O(N) 额外内存换更少重复扫描。需要同时评估缓存上限、失效策略和 OOM 风险。”

  • 看到递归遍历树但没有深度保护

    • “除了时间，还要看栈空间 O(depth)。评论树、目录树过深时会先 StackOverflowError，应改显式栈或限制深度。”

  • 看到 Compose / Flutter 在 UI 更新路径里做集合派生

    • “状态变化会触发重组/rebuild，若每次都 filter/map/sort，就把 O(N) 或 O(N log N) 放进了高频路径。应缓存派生结果、缩小状态影响范围或后台预处理。”

常用数据结构与操作复杂度速查 ​

结构 / 操作常见时间复杂度常见空间特征工程提醒
数组 / List[index]O(1)连续存储随机访问快，中间插删通常不便宜
线性扫描 containsO(N)O(1)小数据没问题，大数据或高频调用会暴露
HashMap.get / HashSet.contains平均 O(1)额外索引空间典型空间换时间
平衡树查找O(log N)节点结构更多需要有序性时有价值
全量排序O(N log N)视实现而定只要 Top-K 时不一定该全排
双重循环两两比对O(N²)常为 O(1)最容易在业务代码里悄悄写出来
递归深遍历时间看逻辑，栈空间常为 O(depth)依赖调用深度时间不炸也可能先栈溢出

Android / Compose / Flutter 主线理解 ​

下面每个案例都按 问题 → 判断 → 原因 → 修法 写完整，便于你直接拿去回答或改代码。

1. Android View / RecyclerView ​

案例 A：打开列表页时主线程全量排序 ​

  • 问题：联系人、消息、评论列表在 onCreate / onResume 里直接 Collections.sort(list)。
  • 判断：排序至少 O(N log N)；若还伴随字符串比较、分组映射、日期格式化，常数更大。
  • 原因：主线程一次要处理完整列表，数据从几百涨到几千时，首屏打开明显变慢。
  • 修法：后台线程预处理；进入页面前分页加载；若只要前 K 条用堆；本地 DB 建索引按字段排序后查询。

案例 B：搜索框每次输入都全量扫描 ​

kotlin
fun onQueryChanged(query: String, allItems: List<Item>): List<Item> {
    return allItems.filter { it.title.contains(query, ignoreCase = true) }
}
  • 问题：用户每敲一个字符，都对全量列表做一次 filter。
  • 判断：单次 O(N)，但触发频率极高；输入 5 个字符就是 5 次全量扫描。
  • 原因：搜索逻辑放在高频回调里，且没有 debounce、没有索引、没有分页。
  • 修法：debounce 300ms；后台线程过滤；本地搜索索引；数据量大时改服务端搜索。

案例 C：RecyclerView 绑定时嵌套线性查找 ​

kotlin
override fun onBindViewHolder(holder: VH, position: Int) {
    val item = items[position]
    val user = allUsers.first { it.id == item.userId } // 每个 item 扫一遍用户表
    holder.bind(item, user)
}
  • 问题：列表有 N 项、用户表有 M 人，绑定时总成本约 O(N × M)。
  • 判断：这是隐性 O(N²)，测试时列表短、用户少，看不出问题。
  • 原因：在滚动路径里重复做线性查找，而不是提前建 Map<Id, User>。
  • 修法：进入页面前 users.associateBy { it.id }；或数据源层 join 好再交给 Adapter。

2. Compose ​

案例 A：重组路径里重复 filter + sort ​

kotlin
@Composable
fun MessageList(messages: List<Message>, keyword: String) {
    val filtered = messages
        .filter { it.content.contains(keyword) }
        .sortedByDescending { it.timestamp }

    LazyColumn {
        items(filtered, key = { it.id }) { message ->
            MessageRow(message)
        }
    }
}

  • 问题：keyword 或 messages 相关状态一变，组合函数可能重新执行，每次都过滤+排序。

  • 判断：filter 约 O(N)，sort 约 O(N log N)，总体约 O(N log N)。

  • 原因：高成本集合计算放在高频重组路径里，而不是提前派生或缓存。

  • 修法：remember(messages, keyword) { ... }；derivedStateOf 缩小重算范围；搜索 debounce；大数据分页。

  • 可能执行顺序

    1. 用户输入触发 keyword 状态变化。
    2. MessageList 重组，重新执行 filter 和 sort。
    3. LazyColumn 用新列表重新布局可见项。

  • 可能输出

    text
    每次击键：O(N) + O(N log N)
N=5_000 时，输入 5 个字符 ≈ 5 次全量重算

  • 预期现象

    • 输入框打字时列表滚动和帧率变差。

  • 观察重点

    • 问题不在 Compose “重组”本身，而在你把集合运算放进了重组路径。

案例 B：状态切分过粗导致整页重算 ​

  • 问题：页面级 mutableStateOf 持有整页数据，改一个开关也触发整页子树重组。
  • 判断：单次操作可能仍是 O(1)，但会连带触发大量子组件重组，常数爆炸。
  • 原因：状态粒度太粗，没有按列表项 / 区块拆分稳定性。
  • 修法：列表项用稳定 key；把搜索词、筛选结果拆成独立 state；子组件参数尽量稳定。

3. Flutter ​

案例 A：build() 里 where().toList()..sort() ​

dart
@override
Widget build(BuildContext context) {
  final visibleItems = items
      .where((e) => e.title.contains(keyword))
      .toList()
    ..sort((a, b) => b.time.compareTo(a.time));

  return ListView.builder(
    itemCount: visibleItems.length,
    itemBuilder: (context, index) => ItemTile(item: visibleItems[index]),
  );
}

  • 问题：每次 setState 后 build() 重新执行，先过滤再排序。

  • 判断：where + toList 约 O(N)，sort 约 O(N log N)。

  • 原因：集合派生放在 rebuild 路径里，而不是 controller / notifier 里提前算好。

  • 修法：在 ChangeNotifier / Bloc 里维护 visibleItems；搜索 debounce；列表分页。

  • 可能执行顺序

    1. setState 触发 build()。
    2. 重新 where、toList、sort。
    3. ListView.builder 用新列表构建可见项。

  • 可能输出

    text
    每次刷新：O(N log N)

  • 预期现象

    • 切 tab、下拉刷新、输入筛选时掉帧。

  • 观察重点

    • Flutter 框架不慢，慢的是 rebuild 前的数据准备。

案例 B：itemBuilder 里再线性查找外部数据 ​

dart
itemBuilder: (context, index) {
  final order = orders[index];
  final user = users.firstWhere((u) => u.id == order.userId);
  return OrderTile(order: order, user: user);
}
  • 问题：每个列表项绑定都扫描一遍 users。
  • 判断：总成本约 O(orders × users)，滚动时持续发生。
  • 原因：没有在数据层提前 Map 索引。
  • 修法：final userById = {for (final u in users) u.id: u}; 后 O(1) 查找；或 join 后下发给 UI。

4. iOS 轻量对照 ​

SwiftUI 的 body 频繁刷新时不要重复做高成本集合运算；大列表筛选、排序、分组不要无脑放进主线程更新路径。复杂度思维跨平台通用，差别主要在框架调度与工具链。

Android / Flutter / Web / Backend 对照 ​

主题Android / KotlinFlutter / DartWeb / Backend关键判断
列表扫描RecyclerView diff、过滤、本地搜索ListView / setState 后重建列表前端搜索、服务端过滤数据量一大，线性扫描就会暴露
空间换时间LruCache、SparseArray、索引表内存缓存、预解码、map 索引Redis、索引表、预计算手机端更受内存上限约束
递归深度树遍历、JSON 解析、目录扫描Widget 树处理、递归渲染服务端 DFS/回溯递归过深会栈溢出，不分平台
排序与 Top-KCollections.sort / PriorityQueue列表排序、堆化服务端排序、排行榜若只要前 K 个，优先考虑堆而不是全排序

常见场景 ​

1. 双重循环查重，改成 HashSet ​

java
boolean contains(List<String> listA, List<String> listB) {
    for (String a : listA) {
        for (String b : listB) {
            if (a.equals(b)) return true;
        }
    }
    return false;
}

boolean containsOptimized(List<String> listA, List<String> listB) {
    Set<String> setB = new HashSet<>(listB);
    for (String a : listA) {
        if (setB.contains(a)) return true;
    }
    return false;
}
  • 可能执行顺序
    1. 原始写法：listA 每个元素都要把 listB 扫一遍。
    2. 优化后：先把 listB 建成索引，再做快速查找。
  • 可能输出
    text
    原始：O(N × M)，N=M=1_000 时约 1_000_000 次比较
优化：O(N + M)，约 2_000 次操作 + O(M) 额外空间
  • 预期现象
    • 数据量一大，优化后延迟下降非常明显。
  • 观察重点
    • 这是标准的“用 O(M) 额外空间，换大量重复时间成本”。

2. 主线程排序大列表导致卡顿 ​

  • 现象：联系人、日志、评论列表在主线程直接排序，页面打开卡顿。
  • 本质：排序通常至少 O(N log N)，如果还伴随对象比较、格式化、分组映射，常数会更大。
  • 修法：后台线程预处理、增量更新、分页加载、提前建索引。

3. 递归遍历树结构没有深度保护 ​

  • 现象：分类树、评论树、目录树在极端数据下崩 StackOverflowError。
  • 本质：不是只有时间复杂度，递归深度还会吃调用栈空间。
  • 修法：改显式栈迭代、限制最大深度、做循环检测。

4. 只要 Top-K，却做了全量排序 ​

  • 现象：排行榜、热搜、推荐列表只要前 10 条，却把 10 万条全排。
  • 本质：全量排序 O(N log N)，Top-K 用堆往往 O(N log K) 且 K 很小时更划算。
  • 修法：PriorityQueue、堆插件、数据库 ORDER BY ... LIMIT K。

常见误配、事故后果与排障 ​

1. 误配：把 benchmark 小样本结果当成长期结论 ​

  • 原因：本地只测了十几条数据，感觉“已经够快”。
  • 后果：线上数据涨上去后 CPU 飙升、首帧卡顿、搜索超时。
  • 排障与修法：先看输入规模上限，再看算法阶数；确认热点后再用 profiler 验证。

2. 误配：只盯时间复杂度，忽略空间复杂度 ​

  • 原因：为了把 O(N²) 改成 O(N)，无脑加巨大缓存。
  • 后果：虽然快了，但移动端触发 OOM、频繁 GC、后台被杀。
  • 排障与修法：明确缓存生命周期、容量上限和淘汰策略，不要把“空间换时间”理解成“无限换”。

3. 误配：把 Big O 当成完整性能答案 ​

  • 原因：看到两个方案都是 O(N)，就断定它们差不多。
  • 后果：忽略对象分配、装箱、锁、IO、重组/rebuild、日志打印等真实成本，优化方向跑偏。
  • 排障与修法：复杂度只负责确定量级，真实性能还要结合 allocation、trace、帧时间一起看。

4. 事故：递归没有去重，指数爆炸 ​

  • 原因：分裂递归里重复求同一子问题。
  • 后果：CPU 打满、超时、ANR，严重时直接被系统判无响应。
  • 排障与修法：看调用栈和 trace 是否反复进入同一方法；能缓存就缓存，能 DP 就 DP。

5. 事故：UI 层嵌套查找，隐性写出平方级复杂度 ​

  • 原因：列表渲染过程中，每个 item 又去线性查找外部信息。
  • 后果：列表越大越卡，滚动和刷新尤其明显。
  • 排障与修法：提前把外部数据建索引，再传给 UI 层消费。

Big O 和真实工程测量怎么配合 ​

复杂度和 benchmark / trace 不是替代关系，而是先后关系：

  1. 先用复杂度做设计判断——提前排除明显会炸的结构，例如高频路径上的 O(N²)。
  2. 再用真实测量验证热点——看 CPU、内存、分配、GC、帧时间、重组次数、布局耗时。
  3. 最后结合场景做取舍——有些 O(N²) 在 N=20 且低频路径里完全可接受；有些 O(N) 在主线程高频输入路径里也会很痛。

复杂度回答“未来放大后会怎样”，profiling 回答“现在到底慢在哪”。

与相近概念对比 ​

概念它回答什么不回答什么
时间复杂度输入规模变大后，执行步骤怎么涨一次真实运行耗时多少毫秒
空间复杂度额外内存怎么涨这块内存是否会被及时回收
均摊复杂度一串操作平均下来每次多贵某次最坏操作是否瞬时卡顿
Benchmark / Profiling真实机器上到底慢在哪若数据量放大后趋势会怎样

对应实验 ​

计划补齐的实验：

Lab说明源码
labs/foundations/complexity-tradeoff-demo/用小样本与大样本对照 O(N²)、O(N log N)、O(N) 的增长差异待补

复习检查题 ​

  1. 为什么说复杂度分析解决的是“增长趋势”，而不是“本机这次跑了多少毫秒”？

    答：因为 Big O 刻意忽略机器、实现细节和一次性环境波动，关注的是输入规模变大后成本如何放大；它告诉你“这类写法未来会不会炸”，而不是替代真实耗时测量。

  2. 为什么很多移动端优化本质上都是“空间换时间”？

    答：因为直接查缓存、查索引、查 HashMap 往往比重复扫描和重复计算更快，但代价是额外内存；移动端优化的关键不是盲目换，而是在流畅度与内存上限之间找平衡。

  3. 为什么两个方案同为 O(N)，线上表现仍可能差很多？

    答：因为 Big O 不描述常数项与工程成本；对象分配、GC、字符串构造、日志打印、布局测量、Compose 重组、Flutter rebuild 等都可能让两个 O(N) 在真实设备上差出数量级。

  4. 为什么 Compose / Flutter 特别容易把复杂度问题“写得很自然”？

    答：因为声明式 UI 会让“状态变化 → 重组/rebuild → 顺手重新 filter/map/sort 一遍数据”看起来很自然；当这些集合运算处在高频 UI 更新路径里时，复杂度问题就会直接变成掉帧问题。

  5. ArrayList.add() 偶尔会扩容拷贝，为什么均摊后还能说是 O(1)？

    答：因为昂贵的扩容不是每次都发生，必须先经历很多次便宜插入才会再来一次；把那次 O(N) 拷贝成本平摊到前面很多次 add 上，平均单次成本仍接近常数级。

  6. 一个递归算法即使“每层工作不重”，为什么仍可能崩在移动端？

    答：因为除了时间，还要看调用栈空间；递归每深入一层就多占一个栈帧，深度过大时会先因为栈空间耗尽而崩掉。

速记 ​

  • 复杂度看趋势，不看一次跑分。
  • 数据加一个零，O(N²) 工作量大约乘一百。
  • 先用 Big O 排雷，再用 trace / profiler 定位真实热点。
  • 移动端最常见优化：用空间换时间，但内存不能无限换。
  • Compose / Flutter 最常见风险：把大集合派生计算放进高频 UI 更新路径。
  • 时间复杂度和空间复杂度要一起看，递归尤其要防栈深。

站点构建时间：2026/08/24 23:45:00

Copyright © 2026-present Engineering Review Lab. All Rights Reserved. (CC BY-NC-SA 4.0)

站点构建时间：2026/8/24 23:43:17

Copyright © 2026-present Engineering Review Lab. All Rights Reserved. (CC BY-NC-SA 4.0)