1. 算法概述

1.1 算法的概念

• 定义：算法（Algorithm）是为解决一个特定问题而规定的一系列定义明确的、有限的、可行的操作步骤。
• 五大基本特性：
  1. 有穷性 (Finiteness)：算法必须在执行有限步之后终止。
  2. 确定性 (Definiteness)：算法的每一步都必须有确切的定义，无歧义。
  3. 可行性 (Effectiveness)：算法中的每一步操作都必须是可执行的，能够通过有限次运算完成。
  4. 输入 (Input)：一个算法有零个或多个输入。
  5. 输出 (Output)：一个算法有一个或多个输出，是算法处理的结果。

1.2 程序与算法的区别

1.3 算法效率的分析

算法效率主要从时间效率和空间效率两个维度来衡量。

1.3.1 时间复杂度 (Time Complexity)

• 定义：指算法执行时间随输入规模 n 增大而变化的趋势。它不是一个精确的执行时间，而是一个增长率的度量。

• 大O表示法 (Big O Notation)：我们通常使用大O表示法来描述时间复杂度，它表示算法执行时间的上界。

• 计算方法：

  1. 识别基本操作：找出算法中执行次数最多的语句。
  2. 建立函数：计算基本操作的执行次数 T(n)，其中 n 是问题规模。
  3. 化简：
     • 忽略所有低阶项。
     • 忽略常数系数。
     • 只保留最高阶项。
  • 例如：如果 T(n) = 3n^2 + 5n + 100，则时间复杂度为 O(n^2)。

• 常见时间复杂度 (从优到劣)：

  • O(1) - 常数阶：代码执行次数与 n 无关。

  def get_first(arr):
      return arr[0]

  • O(log n) - 对数阶：通常见于二分查找、树形结构的操作。

  # 二分查找
  while left <= right:
      mid = (left + right) // 2
      # ...

  • O(n) - 线性阶：需要遍历一遍输入数据。

  def find_max(arr):
      max_val = arr[0]
      for x in arr:
          if x > max_val:
              max_val = x
      return max_val

  • O(n log n) - 线性对数阶：常见于高效的排序算法，如归并排序、快速排序。
  • O(n^2) - 平方阶：通常涉及嵌套循环，如冒泡排序、选择排序。
  • O(n^3) - 立方阶：通常涉及三层嵌套循环，如Floyd算法。
  • O(2^n) - 指数阶：通常见于暴力穷举的递归算法，如斐波那契数列的朴素递归。
  • O(n!) - 阶乘阶：通常见于全排列问题。

1.3.2 空间复杂度 (Space Complexity)

• 定义：指算法在运行过程中临时占用的存储空间大小随输入规模 n 增大而变化的趋势。
• 计算内容：
  • 存储算法本身所占用的空间。
  • 算法的输入输出数据所占用的空间。
  • 算法在运行过程中额外临时占用的空间（重点关注）。
• 常见空间复杂度：
  • O(1)：额外空间是常数级别的，称为原地算法。
  • O(n)：需要一个与输入规模 n 成正比的额外空间，如创建一个新数组。
  • O(n^2)：需要一个 n*n 的二维数组等。
  • 递归栈空间：递归调用的深度也会计入空间复杂度。例如，一个递归深度为 n 的函数，其空间复杂度至少为 O(n)。

2. 递归与分治

2.1 递归 (Recursion)

• 基本原理：一个函数在自己的定义中直接或间接调用自身。
• 递归三要素：
  1. 终止条件 (Base Case)：必须有一个明确的条件，当满足该条件时，递归不再继续，开始返回。这是防止无限循环的关键。
  2. 递归步骤 (Recursive Step)：将原问题分解成一个或多个规模更小的、但与原问题性质相同的子问题。
  3. 函数调用：调用自身来解决这些子问题。
• 递归栈的理解：
  • 每次函数调用时，系统会为其在调用栈 (Call Stack) 上分配一个栈帧 (Stack Frame)。
  • 栈帧用于存储函数的局部变量、参数和返回地址。
  • 当一个函数调用另一个函数（包括自身）时，新的栈帧被压入栈顶。
  • 当函数执行完毕并返回时，其对应的栈帧从栈顶弹出。
  • 优点：代码简洁，逻辑清晰。
  • 缺点：如果递归深度过大，可能导致栈溢出 (Stack Overflow)；重复计算较多时，效率低下。

2.2 分治法 (Divide and Conquer)

• 基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
• 设计三步骤：
  1. 分解 (Divide)：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
  2. 解决 (Conquer)：若子问题规模足够小，则直接求解；否则，递归地解决各子问题。
  3. 合并 (Combine)：将各子问题的解合并，构成原问题的解。

2.3 典型问题及时间复杂性分析

• 时间复杂度分析：分治法的时间复杂度通常用递归式表示：T(n) = aT(n/b) + f(n)
  • a：子问题的数量。
  • n/b：每个子问题的规模。
  • f(n)：分解和合并步骤所需的时间。
  • 可以使用主定理 (Master Theorem) 来求解这种递归式。

4. 动态规划 (Dynamic Programming, DP)

• 基本思想：将一个大问题分解成一系列重叠的子问题，通过存储并重用子问题的解来避免重复计算，从而找到原问题的最优解。
• 适用条件：
  1. 最优子结构 (Optimal Substructure)：一个问题的最优解包含了其子问题的最优解。
  2. 重叠子问题 (Overlapping Subproblems)：在递归求解过程中，许多子问题被反复计算多次。

4.1 动态规划设计四部曲

1. 定义状态 (State)：确定 dp 数组的含义。这是最关键的一步。例如，dp[i] 可能表示“前 i 个元素的最优解”，dp[i][j] 可能表示“对于问题 i 和 j 的最优解”。
2. 找出状态转移方程 (Function)：建立当前状态与之前状态之间的关系式。dp[i] = f(dp[i-1], dp[i-2], ...)。
3. 初始化 (Initialization)：确定 dp 数组的初始值或边界条件。这是递推的起点。
4. 确定计算顺序 (Order)：通常是“自底向上”地进行计算，确保在计算 dp[i] 时，它所依赖的状态都已经被计算出来。

4.2 典型问题应用

• 斐波那契数列：

  • 状态：dp[i] 表示第 i 个斐波那契数。
  • 方程：dp[i] = dp[i-1] + dp[i-2]。
  • 初始化：dp[0] = 0, dp[1] = 1。
  • 复杂度：时间 O(n)，空间 O(n) (可优化至 O(1))。

• 背包问题：

  • 0-1背包问题：N 个物品，一个容量为 W 的背包，每个物品只有一个，有各自的重量 w[i] 和价值 v[i]。求能装入背包的最大总价值。
    • 状态：dp[i][j] 表示从前 i 个物品中选择，放入容量为 j 的背包中所能获得的最大价值。
    • 方程：

    // 如果第 i 个物品的重量大于当前背包容量 j，则不能放入
    if (w[i] > j):
        dp[i][j] = dp[i-1][j]
    // 否则，可以选择放入或不放入
    else:
        dp[i][j] = max(dp[i-1][j],              // 不放入第 i 个物品
                       dp[i-1][j - w[i]] + v[i]) // 放入第 i 个物品

    • 复杂度：时间 O(N*W)，空间 O(N*W) (可优化至 O(W))。

• Floyd-Warshall 算法：

  • 用途：求解任意两点之间的最短路径（所有节点对最短路径），适用于带负权边的图，但不能有负权环。
  • 思想：典型的动态规划。
  • 状态：dp[k][i][j] 表示从顶点 i 到顶点 j，只允许经过 {1, 2, …, k} 作为中间节点的最短路径长度。
  • 方程：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])。
    • dp[k-1][i][j]：不经过 k 的最短路径。
    • dp[k-1][i][k] + dp[k-1][k][j]：经过 k 的最短路径。
  • 实现：通常使用一个二维数组 dp[i][j] 并通过一个 k 循环来更新。

  for k from 1 to n:
      for i from 1 to n:
          for j from 1 to n:
              dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

  • 复杂度：时间 O(n^3)，空间 O(n^2)。

5. 贪心算法 (Greedy Algorithm)

• 基本思想：在每一步决策中，都采取当前状态下最好或最优的选择（即局部最优解），从而希望导致全局最优解。
• 适用条件：
  1. 贪心选择性质 (Greedy Choice Property)：所作的局部最优选择必须能够导致一个全局最优解。这是贪心法最重要的性质，也是最难证明的。
  2. 最优子结构 (Optimal Substructure)：一个问题的最优解包含其子问题的最优解。
• 与动态规划的区别：
  • 决策方式：贪心算法在每一步都做出不可撤销的选择，不关心未来的后果；动态规划会考察所有可能的选择，并从中选出最优的。
  • 求解过程：贪心是自顶向下的，逐步缩小问题规模；动态规划是自底向上的，先解决子问题。
  • 结论：动态规划总能找到最优解，而贪心不一定。能用贪心解决的问题，通常更简单高效。

5.1 典型问题应用

6. 回溯法 (Backtracking)

• 基本思想：一种通过深度优先搜索 (DFS) 来系统地搜索问题解空间的算法。它在搜索过程中，当发现当前路径不可能得到一个有效的解时，就会退回（回溯）到上一步，尝试其他的选择。
• 核心概念：
  • 解空间树：问题的解可以表示为一棵树（或图）的某个节点，回溯法就是在这棵树上进行深度优先搜索。
  • 限界函数/剪枝函数 (Pruning)：这是回溯法与暴力穷举（纯DFS）的关键区别。通过定义一些规则，提前判断当前节点下的子树是否可能包含解，如果不可能，就直接“剪掉”这棵子树，不再进行搜索，从而大幅提高效率。

6.1 算法框架 (伪代码)

result = []
def backtrack(path, choices):
    # 终止条件：如果 path 是一个完整的解
    if is_a_solution(path):
        result.add(path)
        return
 
    # 剪枝：如果当前路径不可能通向一个解
    if cannot_lead_to_solution(path):
        return
 
    # 遍历所有可能的选择
    for choice in choices:
        # 1. 做出选择
        add_choice_to_path(path, choice)
        
        # 2. 进入下一层决策
        backtrack(path, updated_choices)
        
        # 3. 撤销选择 (回溯)
        remove_choice_from_path(path, choice) 

6.2 典型问题应用

• N皇后问题：在一个 N×N 的棋盘上放置 N 个皇后，使得它们不能互相攻击（任意两个皇后不能在同一行、同一列或同一条对角线上）。

  • 搜索：按行放置皇后，在第 i 行尝试所有 N 个列。
  • 剪枝：在尝试放置 (i, j) 位置的皇后时，检查该位置的列、主对角线、副对角线是否已被其他皇后占据。如果被占据，则不放置，直接尝试下一个位置。

• 全排列问题：生成一个集合的所有可能排列。

  • 搜索：依次为排列的每个位置选择一个元素。
  • 剪枝：确保每个元素只被使用一次。可以用一个 used 数组来标记。

• 子集和问题：给定一个集合和一个目标和，找出集合中是否存在一个子集的和等于目标和。

  • 搜索：对于集合中的每个元素，都有“选择”或“不选择”两种可能。
  • 剪枝：如果当前已选元素的和已经超过了目标和，则无需继续向该路径添加元素。

• 时间复杂度分析：回溯法的时间复杂度通常很高，因为它本质上是穷举。复杂度大致为 O(解的数量 * 构造解的时间)。剪枝的好坏直接决定了算法的实际性能，但最坏情况下仍然是指数级的。

复习建议

1. 理解思想：首先要深刻理解每种算法策略的核心思想和适用场景。问自己：这个问题为什么适合用DP？为什么那个问题可以用贪心？
2. 区分对比：重点掌握分治 vs 动态规划，动态规划 vs 贪心，回溯 vs 暴力DFS 之间的区别和联系。
3. 掌握经典：对大纲中提到的每个典型问题，不仅要会解，还要能说出其设计思路、状态定义/贪心策略/剪枝方法以及时空复杂度。
4. 多加练习：算法学习离不开实践。尝试用不同的方法解决同一个问题，加深理解。
5. 总结模板：为回溯法、动态规划等方法总结出自己的代码模板，考试时可以快速套用。

祝你复习顺利，取得好成绩！