数据结构、算法复杂度与工程化解题方法

数据结构决定数据如何组织，算法决定如何变换数据。后端开发并非每天手写红黑树，但需要用复杂度判断集合选择、分页、缓存、调度和热点路径是否会随数据量失控。

1. 学习目标

• 掌握时间/空间复杂度与摊还分析
• 理解线性表、栈、队列、哈希、树、堆、图
• 掌握排序、查找、递归、回溯、贪心和动态规划的适用边界

2. 核心概念

1. 复杂度与输入规模

大 O 描述输入规模增长时资源消耗的上界增长级别，忽略常数与低阶项；Ω 描述下界，Θ 描述紧确界。复杂度必须说明 n 的含义。哈希表平均查找接近 O(1)，但碰撞、扩容和恶意输入会改变成本。

正确边界： 复杂度不是实际毫秒数；性能决策还要用真实数据、缓存局部性、分配和 I/O 基准验证。

2. 线性结构与哈希

数组支持 O(1) 随机访问但中间插入需移动；链表定位第 k 项为 O(n)；栈遵循后进先出，队列遵循先进先出；哈希表用散列函数定位桶并处理冲突。Java 的 ArrayList、ArrayDeque、HashMap 是常用实现。

正确边界： Java 的 Stack 是较旧同步类，栈/队列通常优先 ArrayDeque；HashMap 不保证业务所需顺序。

3. 树、堆与图

二叉搜索树维持有序关系，平衡树控制高度；堆只保证根为最小/最大，适合优先队列；图用顶点和边表达网络、依赖与路径，可用 BFS 求无权最短层数、DFS 做遍历与环检测。

正确边界： 堆不是全排序结构；从 PriorityQueue 迭代得到的顺序不保证有序。

4. 解题模式

双指针和滑动窗口减少重复扫描；前缀和换取区间查询；二分要求单调判定；回溯枚举决策树；动态规划需要定义状态、转移、初值和计算顺序；贪心需要交换论证或不变量。

正确边界： 看到“最优”不代表一定使用动态规划或贪心，先证明重叠子问题、最优子结构或贪心选择性质。

3. 运行链路

4. 最小示例

java复制
static int[] twoSum(int[] values, int target) {
  Map<Integer, Integer> seen = new HashMap<>();
  for (int i = 0; i < values.length; i++) {
    int needed = target - values[i];
    Integer j = seen.get(needed);
    if (j != null) return new int[] {j, i};
    seen.putIfAbsent(values[i], i);
  }
  return new int[0];
}

该实现一次扫描，平均时间 O(n)、额外空间 O(n)。putIfAbsent 保留重复值场景中的较早位置；仍需测试空数组、无解、负数和溢出边界。

5. 练习与验证

1. 实现 LRU 缓存并证明 get/put 的复杂度
2. 用 BFS 求网格最短路径并记录访问集合
3. 为排序实现做随机差分测试

6. 常见误区

• 背题型而不写不变量
• 只写平均复杂度而忽略最坏情况
• 递归未考虑栈深度和重复计算

7. 掌握检查

• 能不用术语堆砌，向初学者解释本主题解决的问题。
• 能运行示例并观察正常、边界和失败分支。
• 能说明该能力在完整 Java 后端链路中的位置和替换边界。
• 能以测试、执行计划、指标或规范条款验证关键结论。

参考资料

• Java Collections Framework
• Princeton Algorithms