Dart Algorithms

Hello 算法 Dart 版 · 完整技能手册

> 来源：靳宇栋《Hello 算法》Dart 语言版 Release 1.3.0，2026 > 蒸馏日期：2026-05-14 | 合并日期：2026-05-15

总目录

• [第一部分：算法思维基础](#第一部分算法思维基础)
• [第二部分：复杂度分析](#第二部分复杂度分析)
• [第三部分：数据结构选择决策](#第三部分数据结构选择决策)
• [第四部分：排序与搜索](#第四部分排序与搜索)
• [第五部分：算法范式对比与选择](#第五部分算法范式对比与选择)
• [第六部分：常见陷阱与反模式](#第六部分常见陷阱与反模式)

---

第一部分：算法思维基础

dart-algorithms-foundations

> 来源：靳宇栋《Hello 算法》Dart 语言版 Release 1.3.0，2026 > 覆盖章节：第 0 章（前言/学习路线）、第 1 章（初识算法）、第 3 章（数据结构分类）

Contents

• [一、为什么要学算法](#一为什么要学算法)
• [二、算法生活类比](#二算法生活类比)
• [三、数据结构分类体系](#三数据结构分类体系)
• [四、三段式学习路线](#四三段式学习路线)
• [五、算法不是万能钥匙](#五算法不是万能钥匙)
• [六、Dart 基础语法在算法中的角色](#六dart-基础语法在算法中的角色)
• [Workflow: 建立算法思维](#workflow-建立算法思维)
• [Examples](#examples)

一、为什么要学算法

R: 原文引用

> 算法是问题的解决方案。在计算机科学中，算法是一系列用于解决特定问题的明确指令。它是计算机程序的灵魂——没有算法的程序只是一堆毫无意义的代码。学习算法不仅是准备技术面试的需要，更是提升工程效率和逻辑思维能力的根本途径。

I: 重述

算法的本质是把"怎么解决问题"变成精确的、可重复执行的步骤序列。学算法有三层价值：第一层是面试通行证——大厂技术面试必考数据结构与算法；第二层是工程效率——知道什么场景用什么结构、算法瓶颈在哪里，写出性能合格的代码；第三层是思维训练——算法教会你的不是死记硬背的模板，而是一种"遇问题 -> 拆解 -> 建模 -> 逐步解决"的思维习惯。这种思维可迁移到任何工程领域。

A1: 书中案例

| 场景 | 算法思维体现 | |------|-------------| | 微信红包分配 | 二倍均值算法在 O(n) 时间内随机拆分金额 | | 导航路径规划 | Dijkstra 最短路径算法在路网图中搜索最优路线 | | 搜索引擎排序 | PageRank 算法用图结构 + 迭代收敛对网页排名 | | 推荐系统 | 协同过滤算法基于用户行为相似性做推荐 | | LeetCode 刷题 | 每道题背后都对应一种或多种算法范式的应用 |

A2: 触发场景

• 刚入门编程，面对算法一词感到困惑和畏惧
• 刷 LeetCode 时不知从何下手，题目和数据结构对不上号
• 面试准备中需要系统了解算法学习的大方向
• 日常开发中遇到性能问题，需要判断"是不是算法选错了"
• 阅读开源项目源码时看到陌生的数据结构想理解其用途

E: 可执行步骤

1. 建立心理锚点：记住一个核心类比——"算法是乐谱，程序是演奏；数据结构是积木块，算法是拼装图纸"
2. 分类你的问题：遇到一个新问题，先判断它属于哪类算法问题——查找、排序、最优化、遍历、规划？
3. 选对数据结构：用什么结构承载数据决定了你后续能做什么操作、能多快完成
4. 动手写代码：看懂不等同于会写。每个算法至少手写 3 遍，能盲打出核心模板
5. 复盘总结：做完一道题后问三个问题——为什么选这个数据结构？复杂度是多少？还有更优解吗？

B: 边界

• 算法不是银弹：很多实际工程问题的瓶颈不在算法而在 I/O、网络、数据库
• 简单场景不用过度设计：20 条数据的列表，线性查找足够，不需要把二分查找包装成服务
• 不是所有问题都有多项式解：NP 难问题（如旅行商问题）只能求近似解
• 面试算法和工程算法有差距：面试追求最优复杂度，工程追求可读、可维护、够用就好

---

二、算法生活类比

2.1 拼装积木——数据结构与算法的共生关系

R：数据结构就像积木的"形状"——有长方形、正方形、三角形；算法就像"拼装步骤"——先拼底座、再搭墙壁、最后盖屋顶。单独看每块积木没什么意义，只有按照一定的顺序和方法把它们组合起来，才能搭出一个完整的作品。

I：数据结构和算法是一体两面。数据结构是数据的组织方式（存储形式），算法是操作数据的方法（执行逻辑）。你无法脱离数据结构讨论算法——二分查找必须在有序数组上运行；你也无法脱离算法讨论数据结构——栈的价值体现在 push/pop 操作的 LIFO 语义上。正确的思维是：先确定需要什么样的数据组织方式，再设计对应的操作方法。

A：以手机通讯录为例——联系人数据用数组（有序存储）存放 -> 支持按姓名二分查找 O(log n)；如果要按标签（如"同事""家人"）分组 -> 改用哈希表（key=标签，value=联系人列表）-> 支持 O(1) 按标签查找。

E：拿到一个需求后，用两个问题启动设计——1. 数据长什么样？（决定结构）2. 我要对它做什么操作？（决定算法）

B：没有"最好的"数据结构，只有"最适合当前场景的"数据结构。

---

2.2 扑克牌排序——插入排序的直觉理解

R：打扑克时拿到一手牌，大多数人会一边摸牌一边整理——从右往左一张张比较，找到合适的位置把新牌插入进去，保持手中的牌始终有序。这个过程就是插入排序的核心思想。

I：插入排序的每个步骤都在维护一个"已排序区间"——初始时是手中的第一张牌（天然有序），每次摸到一张新牌，就在已排序区间中从右往左扫描，找到第一个小于等于新牌的位置，把新牌塞进去。扫描过程中需要把比新牌大的牌整体右移一位。

A：手牌 [5, 2, 4, 6, 1] -> 摸 5（已排序 [5]）-> 摸 2 插入到 5 前（[2,5]）-> 摸 4 插入到 2 和 5 之间（[2,4,5]）-> 摸 6 插到末尾（[2,4,5,6]）-> 摸 1 插到最前（[1,2,4,5,6]）。时间复杂度 O(n^2)，但当牌近乎有序时只需 O(n)——因为每次比较一下就结束，不需要大量右移。

E：

void insertionSort(List nums) {
  final n = nums.length;
  for (var i = 1; i = 0 && nums[j] > base) {
      nums[j + 1] = nums[j];
      j--;
    }
    nums[j + 1] = base;
  }
}

B：数据量超过 10^4 时 O(n^2) 不可接受；反序排列是最坏情况，每次都要移动到最左端。

---

2.3 查字典——二分查找的直觉理解

R：查一本按拼音排序的字典时，你不会从第一页开始逐页翻。你会先翻到中间，看当前页的首字拼音在你目标拼音之前还是之后——如果在之前就翻后半本，在之后就翻前半本。每翻一次查找范围减半，最多翻 log2(n) 次。

I：二分查找的四个前提：1. 数据有序（字典按拼音排序）2. 支持随机访问（能直接翻到任意页）3. 静态或低频更新（字典不会每天重排）4. 不是链表（链表翻到中间需要 O(n) 走一遍）。满足前提时，O(log n) 的效率在 n=10^6 时只需约 20 次比较——这是指数级差距。

A：在 26 个字母的字典中找 "K" 开头的词 -> 翻到中间 (M) -> K 翻到中间 (F) -> K>F，翻后半本 -> 翻到中间 (I) -> K>I，翻后 -> 翻到 (K)，命中。共 4 次翻页（log2 26 ~~ 4.7）。

E：

int binarySearch(List arr, int target) {
  var left = 0, right = arr.length - 1;
  while (left 750 的顺序输出即可，O(n+750) ~~ O(n)。

**E**：

```dart
void countingSort(List nums) {
  if (nums.isEmpty) return;
  final m = nums.reduce((a, b) => a > b ? a : b);
  final counter = List.filled(m + 1, 0);
  for (final num in nums) counter[num]++;
  var i = 0;
  for (var val = 0; val  数据结构的分类可以从两个维度展开。第一个维度是**逻辑结构**——反映数据元素之间的逻辑关系，分为线性和非线性两大类。第二个维度是**物理结构**——反映数据在计算机内存中的存储方式，分为连续存储（数组）和分散存储（链表）。所有复杂数据结构都是数组或链表（或二者组合）在逻辑结构维度上的设计。

### I: 重述

数据结构分类体系的精髓在于：**逻辑结构**描述的是"看起来怎么样"（元素之间的抽象关系），**物理结构**描述的是"放在哪"（内存中的真实布局）。比如说，栈在逻辑上是 LIFO 的线性结构，但在物理上可以用数组（连续空间）或链表（分散空间）两种方式实现。再比如，二叉树在逻辑上是树形结构，但在物理上可以用数组（完全二叉树按层编号存储）或链表节点（左右指针）两种方式实现。理解这两个维度，你就理解了数据结构设计的全部可能性。

### 逻辑结构分类

数据结构（逻辑维度） |-- 线性结构（元素之间是一对一关系） | |-- 数组 —— 索引访问，定长/动态扩容 | |-- 链表 —— 指针串联，增删 O(1) | |-- 栈 —— LIFO，后进先出 | +-- 队列 —— FIFO，先进先出 | +-- 非线性结构（元素之间是一对多/多对多关系） |-- 树 —— 层级关系，一对多（二叉树、堆、AVL） |-- 堆 —— 特殊完全二叉树，用于优先队列 |-- 哈希表 —— 键值映射，O(1) 平均查找 +-- 图 —— 多对多，顶点+边构成网络

### 物理结构对比表

| 维度 | 连续空间（数组） | 分散空间（链表） |
|------|-----------------|-----------------|
| 存储方式 | 一块连续内存，按索引顺序排列 | 节点散落在内存各处，通过指针串联 |
| 随机访问 | O(1) — 通过索引直接定位 | O(n) — 必须从头遍历到目标位置 |
| 插入/删除 | O(n) — 需要移动后续所有元素 | O(1) — 仅修改相邻节点指针（已知位置时） |
| 缓存友好度 | 高 — 连续内存，CPU 缓存预取命中率高 | 低 — 跳转访问，频繁 cache miss |
| 空间开销 | 低 — 仅存数据本身 | 高 — 每节点额外存指针（Dart 对象头更大） |
| 扩容机制 | 动态数组扩容需搬移 O(n)，但均摊 O(1) | 天然动态，无扩容问题 |
| Dart 对应 | `List`（基于数组） | 无内置链表，需自建或 `dart:collection` 的 `LinkedList` |

### A1: 物理结构选择案例

| 场景 | 选择物理结构 | 原因 |
|------|------------|------|
| 算法题中的栈 | 基于数组实现 | 缓存命中率高，操作效率优于链表 |
| 浏览器前进后退 | 基于双向链表 | 频繁在中间删除（关闭标签页），O(1) |
| 大型游戏的场景管理 | 链表 | 频繁增删实体，随机访问不是主力操作 |
| Twitter 时间线 | 数组（动态列表） | 主要操作是按时间顺序追加和遍历显示 |
| LRU 缓存 | 哈希表 + 双向链表 | 哈希 O(1) 查找 + 链表 O(1) 调整顺序 |

### 数据结构设计的三要素

**R**：任何一种数据结构的设计都围绕三个要素展开——**空间占用**（占多少内存）、**操作速度**（各种操作有多快）、**信息表示**（能否准确表达数据之间的关系）。

**I**：三要素是"不可能三角"——你通常只能在三个维度中取其二。数组取"速度快 + 空间小"，牺牲了"增删灵活"；链表取"增删快 + 灵活扩容"，牺牲了"随机访问"和"空间紧致"；哈希表取"查找快 + 表示灵活"，牺牲了"有序性"和"额外空间"；红黑树取"有序 + 平衡"，牺牲了"常数项大 + 额外指针空间"。选择数据结构时，你是在回答：我愿意牺牲哪个指标来换取哪个指标？

**E**：设计或选择数据结构时的评估清单：

1. **画操作贴图**：列出你的代码中每种操作（查/增/删/改/遍历）的频率比例
2. **算空间上限**：估算数据量 n 及上限，确定 O(n) 空间是否可接受
3. **标有序需求**：数据是否需要保持插入顺序、排序顺序、或任意顺序均可
4. **查复杂度正交表**：看哪种结构在最高频操作上有最优复杂度
5. **考虑 Dart 现实**：Dart 内置 `List` 是数组、`Map`/`Set` 是哈希表、`Queue` 基于 `List`——大多数场景不需要手写结构

### B: 数据结构分类边界

- 分类是人为的，不是绝对的：哈希表既可以是"线性结构"（拉链法本质是数组+链表），也可以是"非线性"（键值映射不算线性关系）
- 物理结构不止数组和链表两种：内存池、B+ 树的页式存储等在操作系统/数据库层面才是真实的物理结构
- Dart 层面的"物理结构"被 VM 封装：我们只能控制逻辑组织，无法精确控制内存布局（GC 移动对象对程序员透明）

---

## 四、三段式学习路线

### R: 原文引用

> 本书建议的学习路径分为三个阶段。阶段一：算法入门——先熟悉各种数据结构的特点和用法，能够用代码实现基本操作。阶段二：刷算法题——先刷热门题目，积累 100 道以上的刷题量，在实战中理解算法的应用。阶段三：构建体系——在大量练习后，知识开始融会贯通，此时回头整理知识图谱，形成自己的算法思维体系。

### I: 重述

三段式的核心逻辑是**先广度、后深度、再融通**。阶段一不求精，只求"见过"——你知道数组、链表、栈、队列、哈希、树、堆、图各长什么样、各有什么特点。阶段二是"练内功"——LeetCode 刷题不是目的，是通过大量题的交叉印证，把"冒泡排序 O(n^2)"从背的变成肌肉记忆。阶段三时你不再需要死记模板——看到一个题目，脑子里自动浮现出"这用哈希表 + 双指针就行"的方案。三个阶段缺一不可：不经历阶段一的广度，阶段二就是瞎撞；不经历阶段二的量变，阶段三就永远是别人的经验。

### A1: 书中案例

| 阶段 | 学习内容 | 对应章节 |
|------|---------|---------|
| 阶段一 | 复杂度分析、数据结构遍历、基本排序 | 第 1-11 章 |
| 阶段二 | LeetCode Hot 100、剑指 Offer 等 | 各章配套练习 |
| 阶段三 | 重新整理复杂度速查表、画出个人知识图谱 | 全书回顾 |

### A2: 触发场景

- 不知道从哪本书/哪个章节开始学算法
- 刷了 30 道题感觉没有进步，开始怀疑方法
- 看到 Hard 题就开始发怵，不知道该用什么数据结构
- 面试前几天突击复习，想系统性地过一遍
- 学完一段时间后想检验自己是否真正掌握了

### E: 阶段一可执行清单

1. **跑通环境**：克隆 Hello 算法 Dart 版仓库，运行每个示例代码
2. **画结构图**：用手画出 8 种核心数据结构的逻辑结构和物理存储示意图
3. **默写基本操作**：List 的增删查改、Map/Set 的增删查、链表节点的创建/删除/遍历（手写 3 遍）
4. **理解复杂度**：看到一种数据结构，能立刻说出它的查/增/删复杂度（至少 80% 准确率）
5. **完成阶段性自测**：不看答案实现插入排序、二分查找，验证正确性

### E: 阶段二可执行清单

1. **定计划**：每天 1-3 道题，优先做 LeetCode Hot 100 中你已经认识数据结构的题
2. **记录模板**：每学一个新算法范式，写入个人模板库（分治、回溯、DP、贪心各一个核心模板）
3. **交叉练习**：同一道题尝试用不同数据结构和算法范式解决
4. **复盘瓶颈**：做不出来的题，标注"是数据结构选错了"还是"算法范式不熟"，针对性补
5. **积累 100+**：到达 100 道题时，你应该能对 70% 的 Medium 题在 5 分钟内给出大致思路

### E: 阶段三可执行清单

1. **画知识图谱**：用思维导图或流程图把学过的所有数据结构和算法范式画出来，标出相互引用关系
2. **写 Skill 文档**：参考本书蒸馏技能的格式，把你自己总结的心得写成结构化的 SKILL.md
3. **教别人**：给另一个刚学算法的人讲一遍——如果你能讲清楚，才算真的理解了
4. **写总结文章**：把"数组 vs 链表"、"BFS vs DFS"、"DP vs 贪心"等核心对比写出来

### B: 学习路线边界

- 阶段不可跳跃：没有阶段一的广度就想跳到阶段三的融通 = 空中楼阁
- 刷题量不是唯一指标：100 道题是参考值，有些人需要 200 道，关键是每道题都复盘总结
- 书不是唯一的资源：本书以基础数据结构为主，高级算法（字符串算法、数论、计算几何）需另寻资源
- 算法学习是长期过程：不能指望两周"突击"掌握——把它当成健身，每周保持训练节奏

---

## 五、算法不是万能钥匙

### R: 原文引用

> 虽然算法在计算机科学中占据核心地位，但我们不应神化算法。算法是解决问题的工具，而不是目的。在实际工程中，代码的可读性、可维护性、团队协作效率往往比极致的算法优化更重要。

### I: 重述

算法思维和工程思维有本质区别。算法追求**极端效率**——哪怕常数因子大一倍都要优化；工程追求**恰到好处**——代码要人看得懂、改得动、测得到。你不需要在每个 for 循环前面分析时间复杂度，也不需要把每个缓存都实现成 LRU。真正的能力是"知道什么时候该用算法思维"——当数据量从 1000 变成 1000 万时，当响应延迟从 100ms 飙升到 5s 时，你能迅速定位瓶颈并选择正确的优化策略。

### A: 过度优化的反面案例

| 场景 | 过度优化 | 正确做法 |
|------|---------|---------|
| 配置列表排序 | 10 条配置用自平衡 BST 存储 | `List.sort()` 足够，O(1) 完全可以忽略 |
| 聊天消息列表 | 为找最新消息实现跳表 | 直接在末尾 append，用线性倒查 |
| 单次数据库查询 | 在内存里写复杂的图算法去重 | 让数据库用 DISTINCT 或 GROUP BY |
| 微服务 API | 为省 2ms 延迟把同步改异步 | 除非吞吐量到瓶颈，否则同步更简单、更好调试 |

### E: 判断是否需要算法优化的决策流程

1. **测量，不要猜**：用 profiler 或 benchmark 找出真正的瓶颈，不要凭直觉
2. **算一笔账**：优化带来的性能提升 vs 增加的代码复杂度和维护成本
3. **问一个问题**：这个操作会执行多少次？如果 `n` 永远不会超过 100，O(n^2) 完全 OK
4. **检查已有轮子**：Dart SDK 和常用包里的方法（`sort()`、`where()`、`fold()`）已经高度优化，不要重复发明

### B: 终极边界

- 算法优化有极限：比较排序不能突破 O(n log n) 的理论下界
- 有些问题是 NP 难的：你必须接受近似解，而不是追求最优解
- 代码腐烂速度 > 性能退化速度：三个月后没人能维护的"极致优化"代码，比多跑 500ms 的"朴素实现"更危险
- 过早优化是万恶之源（Donald Knuth）：先让代码正确运行，再让代码跑得快

---

## 六、Dart 基础语法在算法中的角色

### 6.1 变量与类型推断

```dart
// var 类型推断——省去冗长类型声明，保持代码清爽
var count = 0;        // int
var ratio = 3.14;     // double
var flag = true;      // bool
var items = [];  // List

// final vs const——算法中的常量定义
final n = nums.length;          // 运行时确定
const mod = 1000000007;         // 编译时常量，取模用

6.2 集合操作链（Collection If/For）

// 集合字面量中的控制流——比传统 for 循环更声明式
List evenSquares(List nums) {
  return [
    for (final n in nums)
      if (n % 2 == 0) n * n,   // 偶数的平方
  ];
}

// 等价传统写法
List evenSquaresOld(List nums) {
  final result = [];
  for (final n in nums) {
    if (n % 2 == 0) result.add(n * n);
  }
  return result;
}

6.3 可空类型在算法中的安全处理

// null 用于"未找到"的语义
int? findIndex(List nums, int target) {
  for (var i = 0; i ? nums) {
  final n = nums?.length ?? 0;     // 如果 nums 为 null，用 0
  final safe = nums ?? [];          // 给默认空列表
  safe.forEach(print);
}

6.4 Map 和 Set 在算法题中的高频用法

// 两数之和——Map 的经典 O(n) 解法
List twoSum(List nums, int target) {
  final seen = {};  // value -> index
  for (var i = 0; i  nums) {
  final seen = {};
  for (final n in nums) {
    if (!seen.add(n)) return true; // Set.add 返回 false 表示已存在
  }
  return false;
}

// 字符频率统计——Map 计数模式
Map charFrequency(String s) {
  final freq = {};
  for (final ch in s.split('')) {
    freq[ch] = (freq[ch] ?? 0) + 1;
  }
  return freq;
}

6.5 级联操作符（Cascade）

// 级联操作符构建复杂数据结构——链式操作
final graph = >{}
  ..[0] = [1, 2]
  ..[1] = [0, 3]
  ..[2] = [0, 3]
  ..[3] = [1, 2];

// 等价于
final graph2 = >{};
graph2[0] = [1, 2];
graph2[1] = [0, 3];
graph2[2] = [0, 3];
graph2[3] = [1, 2];

E: Dart 语法速查在算法中的应用

| 语法特性 | 算法场景 | 示例 | |---------|---------|------| | ~/ 整除 | 二分查找 mid 计算、取一半 | final mid = (left + right) ~/ 2; | | ?? 空值合并 | 统计计数时初始化 | freq[ch] = (freq[ch] ?? 0) + 1; | | ... 展开 | 合并两个列表（归并排序） | result.addAll(left.sublist(i)); | | collection if/for | 条件过滤、列表推导 | [for (final n in nums) if (n > 0) n] | | Set.add 返回值 | 去重、检测重复 | if (!seen.add(n)) return true; | | reduce | 求和、找最大值 | final max = nums.reduce((a, b) => a > b ? a : b); |

B: Dart 语法边界

• ~/ 是截断除法，不是 round——3 ~/ 2 == 1，不是 2
• List.filled(length, fill) 填充的是同一个对象引用——对 mutable 对象的 filled 要小心
• 集合字面量中的 for/if 会立即执行并构建完整集合——不是惰性的
• Set.add 对已存在元素返回 false，但不会抛出异常——可以作为去重哨兵
• Dart 无内置对 tuple 的语法支持——算法中需要返回多个值时，用 Record（(int, int)）或自定义类

---

Workflow: 建立算法思维

Task Progress

• [ ] Step 1: 理解问题域。 面对一个新问题时，先用自然语言描述清楚——输入是什么？输出是什么？约束条件是什么？（数据范围、时间限制、空间限制）
• [ ] Step 2: 判断算法类型。 是查找（二分/哈希/遍历）？排序（比较/非比较）？最优化（DP/贪心）？遍历（BFS/DFS）？排列组合（回溯）？先贴一个标签。
• [ ] Step 3: 选择数据结构。 根据操作模式（查/增/删哪个多）和有序性需求，从 8 种核心结构中选出候选。对照第 3 章的"不可能三角"做权衡。
• [ ] Step 4: 画流程图 / 状态图。 在纸上画出算法的执行流程——每一步数据如何变化、指针如何移动。不要跳过这一步直接写代码。
• [ ] Step 5: 分析复杂度。 标注时间复杂度和空间复杂度，确认在给定数据范围内是否可行。如 n=10^6 则 O(n^2) 不可用。
• [ ] Step 6: 编写 Dart 代码。 遵循 Effective Dart 风格，使用恰当的 Dart 语法特性（非空类型、集合操作符、final 优先）。
• [ ] Step 7: 测试边界。 测试空输入、单元素、全部相同元素、反序排列等极端情况。用 assert 编写自测用例。
• [ ] Step 8: 复盘 + 找更优解。 做完后问：这是最优复杂度吗？有没有常数项更小的实现？Dart 有没有内置方法可以替代？

条件逻辑

• **如果输入规模 n O(n^2) 算法可接受，优先选择代码简洁的实现
• 如果输入规模 n >= 10^6 -> 必须 O(n) 或 O(n log n)，禁止 O(n^2)
• 如果数据已经有序 -> 优先考虑二分查找 O(log n)，而不是从头遍历
• 如果需要反复查找 -> 构建哈希表（空间换时间），而不是每次线性查找
• 如果问题涉及"全部组合/排列" -> 这是回溯算法的信号，复杂度通常是 O(2^n) 或 O(n!)
• 如果问题求"最大/最小/最优"且有重叠子问题 -> 这是动态规划的信号，先找状态转移方程
• 如果数据范围固定且很小（如 26 个字母） -> 可以用固定大小的数组替代 Map 做计数，O(1) 空间 + O(1) 访问
• 如果 Dart 内置方法能满足需求 -> 不要重复发明轮子。nums.sort()、nums.where()、nums.fold() 已经高度优化

---

Examples

示例 1: 如何判断一个问题属于哪种算法类型

/// 问题：给定一个整数数组，找出其中任意一个重复的数字。
/// 返回重复的数字，如果没有重复则返回 null。

// 判断流程：
// Step 1: 输入 int[]，输出 int?，约束：无（数据范围未指定）
// Step 2: 算法类型标签——"查找重复"
// Step 3: 数据结构选型——
//   方案A: 遍历 + Set 去重 -> O(n) 时间，O(n) 空间
//   方案B: 排序 + 相邻比较 -> O(n log n) 时间，O(1) 空间
// Step 4: 无需复杂流程图，简单的一趟遍历
// Step 5: 方案A 适合 n 不大时；方案B 适合内存紧张时

int? findDuplicate(List nums) {
  final seen = {};
  for (final n in nums) {
    if (!seen.add(n)) return n; // Set.add 返回 false = 已存在
  }
  return null;
}

// 自测用例
void main() {
  assert(findDuplicate([1, 3, 4, 2, 2]) == 2);
  assert(findDuplicate([3, 1, 3, 4, 2]) == 3);
  assert(findDuplicate([1, 2, 3, 4]) == null);
  assert(findDuplicate([1]) == null);
  assert(findDuplicate([]) == null);
}

示例 2: 数据结构选择决策——同一个问题，三种方案

/// 问题：设计一个支持"插入"和"获取中位数"的数据结构
/// 展示了数据结构选择如何改变算法策略

// 方案A: 无序数组 + 每次查询时排序
// 插入 O(1)，查询 O(n log n) —— 适合写多读少的场景
class MedianFinderA {
  final List _data = [];

  void addNum(int num) => _data.add(num); // O(1)

  double findMedian() {
    _data.sort(); // O(n log n)
    final mid = _data.length ~/ 2;
    if (_data.length % 2 == 1) return _data[mid].toDouble();
    return (_data[mid - 1] + _data[mid]) / 2.0;
  }
}

// 方案B: 两个堆（大顶堆 + 小顶堆）
// 插入 O(log n)，查询 O(1) —— 适合读多写多
import 'dart:collection';

class MedianFinderB {
  final _lo = HeapPriorityQueue((a, b) => b.compareTo(a)); // 大顶堆
  final _hi = HeapPriorityQueue(); // 小顶堆（默认）

  void addNum(int num) {
    _lo.add(num);
    _hi.add(_lo.removeFirst());
    if (_lo.length  _hi.length) return _lo.first.toDouble();
    return (_lo.first + _hi.first) / 2.0;
  }
}

示例 3: 递归思维入门——从迭代到递归的思维转换

/// 计算 1+2+...+n，用两种方式实现，体会递归的递与归

// 迭代版——显式循环，状态在迭代中累加
int sumIterative(int n) {
  var result = 0;
  for (var i = 1; i  List.generate(n, (i) => i + 1).fold(0, (a, b) => a + b);

示例 4: 复杂度分析的实战流程

/// 问题：判断一个整数 n 是否为质数
/// 不同实现有不同的复杂度——展示从 O(n) 到 O(sqrt(n)) 的优化

// 版本1: 暴力试除法 —— O(n) 时间，O(1) 空间
bool isPrimeV1(int n) {
  if (n ? nums, int target) {
  // 边界1: null 或空列表
  if (nums == null || nums.isEmpty) return null;

  var left = 0;
  var right = nums.length - 1;

  // 边界2: 单元素列表
  if (left == right) return nums[left] == target ? left : null;

  while (left  时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。"时间增长趋势"这个概念很抽象，我们通过一个例子来理解。假设输入数据大小为 n，给定三个算法 A、B、C，它们分别执行 1 次、n 次、n² 次操作。从增长趋势来看，足够大的 n 会使得不同阶数之间的差距变得巨大，因此我们通常只关注最高阶的项。

*—— 靳宇栋《Hello 算法》Dart 版，第 2 章*

## I: 方法论重述

复杂度分析的本质是**忽略常数因子、只关注增长趋势的渐进性思维**。大 O 表示法给出了一个函数在 n→∞ 时的上界。这个方法论的三个支柱：

1. **以操作为单位**：不直接计时（受硬件影响），而是统计基本操作（赋值、比较、算术、函数调用）的执行次数。
2. **推算渐近上界**：从统计到的操作数 f(n) 出发，找到增长阶最高的项，忽略常数系数和低阶项，得到 O(g(n))。
3. **最差情况优先**：通常取最坏输入下的操作数作为复杂度，因为它给出了算法的性能底线。

两个关键技巧：**乘法法则**（嵌套循环各层相乘）和**加法法则**（顺序执行各步相加再取最高阶）。递归的复杂度分析需要额外的手段——递归树法或主定理。

## A1: 书中经典案例

| 案例 | 复杂度 | 关键特征 |
|------|--------|----------|
| 数组随机访问 | O(1) | 通过索引直接定位，操作次数不随 n 增大 |
| 二分查找 | O(log n) | 每次比较将问题规模减半 |
| 线性查找 | O(n) | 最坏情况下遍历整个数组 |
| 冒泡排序 | O(n²) | 双层嵌套循环，每层遍历约 n 次 |
| 递归斐波那契 | O(2ⁿ) | 每次调用分裂为两个子问题，呈指数增长 |
| 全排列 | O(n!) | 第一个位置有 n 种选择，第二个有 n−1 种，以此类推 |
| 归并排序（递归树） | O(n log n) | log n 层递归，每层合并操作 O(n) |
| 递归求和（尾递归） | O(n) | 线性递归，每层 O(1)，共 n 层 |

## A2: 未来触发场景

用户有以下需求时应加载本技能：

- 编写算法后不确定其性能瓶颈在哪里
- 比较多个解决方案时无法量化判断谁更优
- 设计递归函数需要评估栈深度和总操作量
- 面试准备、Code Review 中需要论证代码效率
- 数据规模从几百增长到百万级别，需要预估是否有性能风险
- 权衡"时间换空间"或"空间换时间"的架构决策

## E: 可执行步骤

### Step 1: 确定输入规模 n

明确 n 代表什么——数组长度、节点数、字符串长度、递归深度等。

### Step 2: 统计基本操作数

逐行遍历代码，为每行标注执行次数（用 n 表示），累加得到 f(n)：
- 简单语句（赋值、return）：计数 1
- 循环体：循环次数 × 循环体内操作数
- 条件分支：取分支中最大操作数（最差情况）
- 函数调用：计入被调用函数的操作数

### Step 3: 应用大 O 化简规则

从 f(n) 提取渐近上界：
1. 保留最高阶项（忽略低阶项）
2. 忽略常数系数
3.

…

## Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

- **Author:** [Python51888](https://github.com/Python51888)
- **Source:** [Python51888/StudyDart-Skills](https://github.com/Python51888/StudyDart-Skills)
- **License:** BSD-3-Clause
- **Homepage:** https://zread.ai/Python51888/StudyDart-Skills

Install and usage instructions live in the source repository linked above.