算法

算法是解决特定问题的有限、确定、可行的步骤序列，是计算机科学的核心基础。以下从基础概念、核心知识点到经典应用，系统梳理算法的相关内容：

一、算法的基本概念

1. 定义：算法是对解决问题的步骤描述，需满足“给定输入，在有限步骤内输出正确结果”。

   • 与“程序”的区别：算法是抽象的逻辑步骤（不依赖编程语言），程序是算法的具体实现（可能包含语法细节）。

2. 核心特性（判断一个过程是否为算法的标准）：

   • 输入：有 0 个或多个外部输入（如问题的初始数据）。
   • 输出：至少有 1 个输出（问题的解）。
   • 有穷性：步骤有限（不能无限循环）。
   • 确定性：每个步骤的含义明确（无歧义）。
   • 可行性：步骤可通过有限次基本操作实现（如加减、比较等）。

二、算法的复杂度分析

复杂度是衡量算法效率的核心指标，分为时间复杂度和空间复杂度，均关注“输入规模 n 增长时，资源消耗的增长趋势”（忽略常数因子和低阶项）。

1. 时间复杂度（Time Complexity）

• 定义：算法执行基本操作次数随输入规模 n 的增长趋势（而非实际运行时间，因实际时间受硬件/语言影响）。

• 表示方法：大 O 记号（O()），如 O(f(n))，其中 f(n)是 n 的函数。

• 计算规则：

  • 只保留最高阶项（如 3n²+2n+5 → O(n²)）。
  • 忽略常数系数（如 2logn → O(logn)）。

• 常见复杂度等级（从优到劣）：
  O(1)（常数阶，如数组访问）→ O(logn)（对数阶，如二分查找）→ O(n)（线性阶，如线性查找）→ O(nlogn)（线性对数阶，如快速排序）→ O(n²)（平方阶，如冒泡排序）→ O(n³)（立方阶，如矩阵乘法）→ O(2ⁿ)（指数阶，如未优化的斐波那契递归）→ O(n!)（阶乘阶，如旅行商问题暴力解）。

• 复杂度场景：

  • 最好情况：输入最理想时的复杂度（如二分查找找到第一个元素，O(1)）。
  • 最坏情况：输入最差时的复杂度（如二分查找找不到元素，O(logn)）。
  • 平均情况：所有输入的复杂度加权平均（更接近实际，但计算复杂）。

2. 空间复杂度（Space Complexity）

• 定义：算法执行时临时占用存储空间随输入规模 n 的增长趋势（不包含输入本身的空间）。
• 常见场景：
  • O(1)：空间不随 n 增长（如变量交换）。
  • O(n)：需要线性空间（如数组存储中间结果）。
  • O(n²)：需要二维空间（如动态规划的二维表）。

三、算法的设计方法

算法设计是解决问题的核心思路，常见方法如下：

1. 枚举法（穷举法）

   • 思想：逐一尝试所有可能的解，验证是否符合条件。
   • 适用场景：解空间小、逻辑简单的问题（如密码破解、小规模组合问题）。
   • 示例：百钱买百鸡问题、判断素数（试除法）。
   • 优缺点：简单直接，但效率低（复杂度高）。

2. 递归与迭代

   • 递归：函数自身调用自身，将大问题分解为同类子问题（需明确“终止条件”和“递推关系”）。
     • 示例：斐波那契数列（朴素递归效率低，因重复计算）、阶乘、树的遍历。
     • 缺点：可能导致栈溢出（递归深度过大）、重复计算（需优化）。
   • 迭代：通过循环重复执行步骤（替代递归，减少栈开销）。
     • 示例：用 for 循环计算斐波那契数列。

3. 分治法（Divide and Conquer）

   • 思想：“分而治之”——将大问题分解为独立的子问题，解决子问题后合并结果。
   • 步骤：分解（拆分子问题）→ 解决（子问题足够小则直接求解）→ 合并（子结果汇总）。
   • 适用场景：子问题与原问题结构一致、可独立求解（无重叠子问题）。
   • 示例：归并排序（拆分数组 → 排序子数组 → 合并）、快速排序（选基准 → 分区 → 递归排序）、二分查找。

4. 动态规划（Dynamic Programming, DP）

   • 思想：解决有重叠子问题和最优子结构的问题——通过存储子问题的解（“记忆化”），避免重复计算。
   • 核心：定义“状态”（子问题的表示）和“转移方程”（子问题间的关系），用表格/数组存储中间结果。
   • 适用场景：优化递归中的重复计算（如斐波那契数列）、最优决策问题（如最短路径、资源分配）。
   • 示例：
     • 斐波那契数列（dp[n] = dp[n-1] + dp[n-2]，存储已计算的 dp[i]）。
     • 背包问题（0-1 背包：dp[i][j]表示前 i 件物品装入容量 j 的最大价值）。
     • 最长公共子序列（LCS）、最长递增子序列（LIS）。

5. 贪心算法（Greedy Algorithm）

   • 思想：每一步都做出当前最优选择（局部最优），期望最终得到全局最优。
   • 适用场景：问题具有“贪心选择性质”（局部最优可导致全局最优），如区间调度、哈夫曼编码。
   • 示例：
     • 找零钱（优先用最大面额硬币）。
     • 哈夫曼编码（每次合并频率最低的两个节点）。
     • 活动选择问题（选结束最早的活动，最大化活动数量）。
   • 局限性：并非所有问题适用（如背包问题中，贪心可能得不到最优解）。

6. 回溯法（Backtracking）

   • 思想：“试错”——逐步构建解，若当前步骤不符合条件则“回溯”（撤销选择），尝试其他路径。
   • 适用场景：解空间大但需找到所有/部分可行解（如排列组合、约束满足问题）。
   • 示例：N 皇后问题（摆放皇后 → 检查冲突 → 冲突则回溯）、全排列问题、子集问题。

7. 分支限界法（Branch and Bound）

   • 思想：类似回溯法，但通过“界限”剪枝（舍弃不可能得到最优解的子树），更高效。
   • 适用场景：优化问题（如旅行商问题 TSP，找最短路径）。
   • 与回溯法的区别：回溯法关注“所有解”，分支限界法关注“最优解”。

8. 哈希法（Hashing）

   • 思想：通过哈希函数将数据映射到存储空间，实现 O(1)级别的查找/插入/删除。
   • 核心：哈希函数设计（减少冲突）、冲突解决（开放寻址、链表法）。
   • 示例：哈希表查找、字符串匹配（Rabin-Karp 算法，用哈希值比较子串）。

四、经典算法问题分类

1. 排序算法

• 比较类排序（通过比较元素大小排序）：
  • 冒泡排序（O(n²)，稳定，简单）、选择排序（O(n²)，不稳定，交换少）、插入排序（O(n²)，稳定，适合小规模数据）。
  • 快速排序（O(nlogn)，不稳定，平均效率高）、归并排序（O(nlogn)，稳定，需额外空间）、堆排序（O(nlogn)，不稳定，利用堆结构）。
• 非比较类排序（不依赖比较，受数据范围限制）：
  • 计数排序（O(n+k)，k 为数据范围，适合整数）、基数排序（O(d*(n+k))，d 为位数，适合多位数）。

2. 查找算法

• 线性查找（O(n)，遍历所有元素）。
• 二分查找（O(logn)，要求有序数组，每次缩小一半范围）。
• 树查找（二叉搜索树 BST：O(logn)平均，O(n)最坏；平衡树如 AVL、红黑树：O(logn)稳定）。
• 哈希查找（O(1)平均，依赖哈希函数）。

3. 图算法

• 遍历：深度优先搜索（DFS，递归/栈实现）、广度优先搜索（BFS，队列实现）。
• 最短路径：
  • Dijkstra 算法（单源最短路径，边权非负）。
  • Floyd-Warshall 算法（多源最短路径，支持负权但无负环）。
  • Bellman-Ford 算法（单源，支持负权，检测负环）。
• 最小生成树（MST）：
  • Kruskal 算法（按边权排序，用并查集避免环）。
  • Prim 算法（从顶点出发，逐步扩展树）。
• 拓扑排序（有向无环图 DAG，用于任务调度）。

4. 字符串算法

• 模式匹配：暴力匹配（BF，O(n*m)）、KMP 算法（预处理模式串，O(n+m)，利用前缀函数减少回溯）、BM 算法、Rabin-Karp 算法（哈希匹配）。
• 字符串编辑距离（计算两个字符串的最小修改次数，动态规划）。

五、算法的评价与衡量标准

• 正确性：能在有限步骤内输出正确结果（需证明，如数学归纳法）。
• 效率：时间复杂度和空间复杂度（优先优化时间）。
• 可读性：步骤清晰，便于理解和维护（如伪代码比机器码易读）。
• 健壮性：能处理异常输入（如空值、越界数据），避免崩溃。

六、高级概念

• NP 问题与 P 问题：
  • P 问题：可在多项式时间（O(nᵏ)）内解决的问题（如排序、二分查找）。
  • NP 问题：可在多项式时间内验证解的正确性，但求解可能需要指数时间（如旅行商问题、NP 完全问题）。
  • 核心未解问题：P=NP？（若成立，所有 NP 问题都有多项式解法）。
• 随机化算法：引入随机选择（如快速排序的基准选择），降低最坏情况概率。
• 并行算法：利用多线程/多进程同时执行步骤（如并行排序），提升效率。

总结

算法是解决问题的逻辑框架，其核心在于“高效”与“正确”。掌握算法需理解设计思想（如分治、DP）、复杂度分析，并通过经典问题（排序、图、字符串）实践应用。无论是开发、科研还是面试，算法都是衡量逻辑思维和问题解决能力的核心指标。