算法面试先从约束和复杂度出发，再选择能够保持清晰不变量的排序或扫描方案。

🧭 什么时候考虑这个专题

小规模或近乎有序数据可考虑简单排序；需要稳定性或可预测上界时优先归并；区间问题常先排序再扫描。

开始编码前先明确输入、输出、数据规模和允许修改的数据，再用一句话写出循环、窗口、堆或递归函数保持的不变量。

核心结构与复杂度

知识点核心规则常见复杂度
顺序与嵌套复杂度顺序代码取主导项，真正嵌套且相互独立的循环通常相乘取决于循环结构
摊还复杂度摊还分析把一系列操作的总成本均摊到每次操作动态数组追加摊还 O(1)
稳定排序稳定排序会保持相等键元素的原始相对顺序取决于具体排序
约束驱动选型输入规模与数据结构决定可接受的复杂度上限由约束决定
递归空间递归调用栈属于额外空间并随最大递归深度增长通常 O(depth)

复杂度必须对应真实代码路径。哈希结构要区分平均与最坏情况，递归要计算调用栈，返回结果是否计入空间也应按题目口径说明。

适用边界

  • 顺序与嵌套复杂度： 循环边界相关时必须按实际执行次数求和
  • 摊还复杂度： 单次扩容仍可能是 O(n)
  • 稳定排序： 只有业务依赖次级顺序时稳定性才影响结果
  • 约束驱动选型： 同一问题在不同约束下可能选择不同算法
  • 递归空间： 是否计入返回结果空间需要按题目口径说明

C# 实现检查

  1. 方法签名与题目契约一致，不依赖控制台输入输出。
  2. 数值计算检查 int 溢出，必要时先提升为 long。
  3. 集合选择说明平均复杂度、顺序语义和重复值处理。
  4. 字符串题明确使用 char、Rune、序号比较还是文化比较。
  5. 递归题说明终止条件、最大深度和退化输入。

⚠️ 常见误区

  • 顺序与嵌套复杂度： 不要把“看到两个循环就一律判定为 O(n²)”当成规则。
  • 摊还复杂度： 不要把“摊还 O(1) 表示每一次操作都严格 O(1)”当成规则。
  • 稳定排序： 不要把“排序结果相同就说明算法一定稳定”当成规则。
  • 约束驱动选型： 不要把“只要算法理论上正确就无需考虑数据规模”当成规则。
  • 递归空间： 不要把“没有显式分配集合就一定是 O(1) 空间”当成规则。

练习顺序

先完成本组 5 道选择题，口述每个选项的边界；再独立实现编程题，最后对照参考答案检查不变量、复杂度和面试追问。