算法分析与设计

Appearance

第3章 排序与查找——从确定性到概率性的思想跃迁 ​

一个关于"极限"的故事 ​

2023年，某搜索团队的工程师小张接到一个任务：优化搜索排序服务。

现有系统对 10^8 条数据做相关性排序，耗时约 2.6 秒。产品经理问："能更快吗？"

小张分析了一下，n = 10^8，lg n ≈ 26，快排需要约 n lg n ≈ 2.6 × 10^9 次比较。他问 Cursor："有没有更快的排序？"

Cursor 回答："试试计数排序，O(n) 线性时间。"

小张照做了。测试环境用 100 条数据，完美通过。他满怀信心地部署上线。

系统崩溃了。

问题出在哪里？

计数排序要求键值范围 k ≤ n。但搜索排序的键是浮点数相关性得分，范围远超 n。Cursor 不知道这个前提条件，小张也没问——两人都错了。

这个故事的教训是：算法有理论极限，也有适用条件。知道极限在哪里，才知道什么时候"能突破"，什么时候"不能突破"。

确定性排序的理论极限是 Ω(n lg n)。想突破这个极限，必须引入额外信息（比如键值范围有限）或接受概率性保证（比如期望复杂度）。

而"接受概率性保证"，正是理解 LLM 采样策略的关键。Temperature > 0 引入随机性，不是缺陷，是设计——就像哈希函数引入随机性，用期望 O(1) 换取可能的最坏 Θ(n)。

这一章的核心叙事 ​

这一章的独特逻辑不是"排序算法有哪些"，而是从确定性到概率性的思想跃迁。

确定性排序 → 理论极限 → 必须引入随机性 → 随机化作为设计 → LLM采样

3.1 排序理论极限 (Ω(n lg n))
   ↓ "确定性排序有其理论极限，要突破必须引入随机性"

3.2-3.4 确定性算法（插入、归并、快排、堆排序）
   ↓ "快排期望 O(n lg n) 但依赖输入分布"

3.3 随机化快排
   ↓ "随机化消除对输入分布的依赖"

3.5 线性时间排序（逃逸下界）
   ↓ "非比较排序可以突破 Ω(n lg n)"

3.7 哈希（随机化作为设计原则）
   ↓ "哈希不是技巧，是随机化算法"

→ LLM 采样策略（随机性是设计，不是缺陷）

学完这一章，你将理解：

  • 为什么确定性排序有 Ω(n lg n) 的下界，什么时候能突破
  • 随机化如何消除对输入分布的依赖
  • 哈希为什么是"随机化算法"，不是"数据结构技巧"
  • LLM 的 Temperature、Top-k、Top-p 采样如何继承随机化算法的设计哲学

如何阅读这一章 ​

这一章的内容需要你有一定编程基础。如果你已经熟悉排序算法，可以重点关注：

  • 3.1 理论极限：决策树下界的证明，信息论视角
  • 3.3 分治排序：快排期望分析，指示器随机变量的巅峰应用
  • 3.7 哈希：Skiena 的视角转换——哈希是随机化算法
  • 3.11 LLM 连接：哈希设计原则如何应用于采样策略

每节都有三层练习：

  • 层次一（基础）：手工计算、证明验证
  • 层次二（LLM 协同）：让 agent 实现，你审查和评判
  • 层次三（Agent 设计）：设计一个 Skill 或策略选择器

本章各节 ​

关键参考文献 ​

本章引用的主要教材和论文：

  • CLRS, Introduction to Algorithms, 4th ed., Chapters 6-11, 25
  • Skiena, The Algorithm Design Manual, 3rd ed., Chapters 4-5
  • Sedgewick & Wayne, Algorithms, 4th ed., Chapters 2-4
  • "The Probability Spaces of QuickSort", arXiv 2025-06
  • "Structure Development in List-Sorting Transformers", arXiv 2025-01
  • "Top-H Decoding: Bounded Entropy", arXiv 2025-09

新时代的算法课程