一、算法的基本概念

1. 定义与特性

   • 算法是解决问题的明确步骤，具备 输入、输出、确定性、有限性、有效性 五大特性。
   • 例：排序算法的输入是数组，输出是有序数组。

2. 复杂度分析

   • 时间复杂度：用大 O 符号（O(n)）表示算法执行时间随输入规模增长的速率。
     • 常见复杂度：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
   • 空间复杂度：算法运行所需内存空间的增长趋势。

---

二、核心数据结构

1. 线性结构

   • 数组：连续内存存储，支持随机访问（O(1)），但插入/删除效率低（O(n)）。
   • 链表：非连续存储，插入/删除高效（O(1)），但访问需遍历（O(n)）。
   • 栈（LIFO）：用于函数调用、括号匹配等场景。
   • 队列（FIFO）：应用于广度优先搜索（BFS）、任务调度。

2. 非线性结构

   • 树：二叉树、二叉搜索树（BST）、平衡树（AVL、红黑树）等，用于快速查找（O(log n)）。
   • 图：由节点和边构成，用于社交网络、路径规划等。
   • 哈希表：通过哈希函数实现 O(1)时间的数据存取，需处理冲突（开放寻址、链地址法）。
   • 堆：优先队列的实现基础，支持快速获取最大/最小值。

---

三、常见算法分类

1. 排序算法

   • 基础排序：冒泡排序（O(n²)）、插入排序（O(n²)）。
   • 高效排序：快速排序（平均 O(n log n)）、归并排序（稳定，O(n log n)）、堆排序。
   • 特殊场景：计数排序、基数排序（适用于整数范围有限的情况）。

2. 搜索算法

   • 顺序搜索：O(n)，适用于无序数据。
   • 二分查找：O(log n)，要求数据有序。
   • 深度优先搜索（DFS）与广度优先搜索（BFS）：用于树/图的遍历。

3. 递归与分治

   • 递归：通过函数自调用解决问题（例：阶乘、斐波那契数列），需注意终止条件与重复计算。
   • 分治：将问题拆解为子问题（例：归并排序、快速排序）。

4. 动态规划（DP）

   • 通过保存子问题结果避免重复计算，适用于重叠子问题和最优子结构。
   • 典型问题：背包问题、最长公共子序列（LCS）、最短路径（Floyd-Warshall）。

5. 贪心算法

   • 每一步选择局部最优解，可能无法得到全局最优。
   • 应用场景：Dijkstra 算法、霍夫曼编码、活动选择问题。

6. 回溯与剪枝

   • 通过试错探索所有可能解，无效路径及时回溯（例：N 皇后问题、数独求解）。
   • 分支限界法：结合剪枝与优先队列，用于优化搜索空间。

---

四、高级算法主题

1. 图算法

   • 最短路径：Dijkstra（单源无负权边）、Bellman-Ford（含负权边）、Floyd-Warshall（多源）。
   • 最小生成树：Prim 算法（贪心）、Kruskal 算法（并查集）。
   • 拓扑排序：用于任务调度、依赖解析。

2. 字符串匹配

   • KMP 算法（利用前缀表跳过不匹配字符）、Rabin-Karp（哈希滚动匹配）。

3. 高级数据结构

   • 并查集（Disjoint Set）：处理集合合并与查询。
   • 字典树（Trie）：高效存储与查询字符串。
   • 跳表：支持快速查找的有序链表。

---

五、算法设计策略

1. 暴力法：穷举所有可能解（例：全排列），通常效率低但易于实现。
2. 增量法：逐步构建解（例：插入排序）。
3. 随机化算法：利用随机性提升效率（例：快速排序的随机化版本）。

---

六、实际应用注意事项

1. 数据规模：根据输入规模选择合适算法（例：小数据用冒泡排序，大数据用快速排序）。
2. 边界条件：处理空输入、极值、重复数据等特殊情况。
3. 代码可读性 vs 性能优化：在可维护性和效率间权衡。
4. 空间换时间：如哈希表用额外空间降低时间复杂度。

---

七、学习路径建议

1. 第一步：掌握复杂度分析与基本数据结构（数组、链表、栈、队列）。
2. 第二步：学习排序、搜索、递归、分治等基础算法。
3. 第三步：攻克动态规划、贪心算法、回溯等难点。
4. 第四步：通过 LeetCode、Codeforces 等平台刷题巩固。

推荐书籍：《算法导论》（理论全面）、《算法（第 4 版）》（Java 实现）、《剑指 Offer》（面试向）。

理解算法基础后，可进一步学习机器学习算法、分布式算法等高级领域。