分治算法、动态规划、贪心算法、分支限界法和回溯算法的深度对比

1. 分治算法 (Divide and Conquer)

核心思想

• 分治法三步曲：
  1. 分解（Divide）：将原问题拆分为多个子问题
  2. 解决（Conquer）：递归解决子问题
  3. 合并（Combine）：合并子问题的解得到原问题的解
• 适用场景：子问题相互独立（无重叠）

典型应用

• 归并排序
• 快速排序
• 大整数乘法

1.分治算法（归并排序）

import java.util.Arrays;public class DivideAndConquer {// 归并排序的主函数public static void mergeSort(int[] arr) {// 如果数组为空或长度小于等于1，则直接返回if (arr == null || arr.length <= 1) return;// 创建一个临时数组用于合并过程中存储数据int[] temp = new int[arr.length];// 调用递归的归并排序函数，传入左边界、右边界和临时数组mergeSort(arr, 0, arr.length - 1, temp);}// 递归的归并排序函数，负责数组的分解和合并private static void mergeSort(int[] arr, int left, int right, int[] temp) {// 递归终止条件：当left >= right时，数组已经是单元素或空数组，不需要再分解if (left < right) {// 计算中间点int mid = left + (right - left) / 2;// 分别对左半部分和右半部分递归排序mergeSort(arr, left, mid, temp);      // 递归排序左半部分mergeSort(arr, mid + 1, right, temp); // 递归排序右半部分// 合并两个已排序的部分merge(arr, left, mid, right, temp);   // 合并两部分}}// 合并两个已排序的子数组private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left, j = mid + 1, k = 0;// 比较并合并两个部分，直到一个部分被完全合并while (i <= mid && j <= right) {if (arr[i] < arr[j]) {// 如果左部分元素小于右部分元素，将左部分元素加入临时数组temp[k++] = arr[i++];} else {// 否则将右部分元素加入临时数组temp[k++] = arr[j++];}}// 如果左部分还有剩余，直接加入临时数组while (i <= mid) temp[k++] = arr[i++];// 如果右部分还有剩余，直接加入临时数组while (j <= right) temp[k++] = arr[j++];// 将临时数组中的数据拷贝回原数组System.arraycopy(temp, 0, arr, left, k);}public static void main(String[] args) {// 定义一个待排序的数组int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};// 调用归并排序进行排序mergeSort(arr);// 输出排序后的结果System.out.println("归并排序结果: " + Arrays.toString(arr));}
}

主要流程：

1. mergeSort：主函数，检查数组的有效性，并创建一个临时数组，然后调用递归函数。
2. mergeSort（递归）：将数组分解成更小的部分，直到每个部分只有一个元素。
3. merge：合并两个已排序的子数组，返回一个合并后的排序数组。

归并排序的工作原理：

1. 分解：递归将数组不断划分为两个子数组，直到每个子数组的长度为1。
2. 合并：通过 merge 函数将两个有序的子数组合并成一个更大的有序数组。

输出：

当运行时，程序会打印排序后的数组：

归并排序结果: [1, 2, 3, 4, 5, 6, 7, 8]

时间复杂度：

归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。尽管归并排序的空间复杂度相对较高（O(n)），但它稳定并且适用于大规模数据的排序。

2. 动态规划 (Dynamic Programming)

核心思想

• 递推优化：通过存储子问题的解（记忆化表），避免重复计算
• 适用场景：存在重叠子问题和最优子结构（如最短路径、背包问题）

动态规划两要素

1. 状态转移方程（递推公式）
2. 边界条件

典型应用

• 斐波那契数列（记忆化优化）
• 0-1背包问题
• 最长公共子序列（LCS）

2. 动态规划（0-1背包问题）

public class DynamicProgramming {// 0-1背包问题的动态规划解法public static int knapsack(int[] weights, int[] values, int capacity) {int n = weights.length; // 物品的数量// dp[i][w]表示前i个物品，背包容量为w时的最大价值int[][] dp = new int[n + 1][capacity + 1];// 遍历每个物品for (int i = 1; i <= n; i++) {// 遍历每个可能的背包容量for (int w = 1; w <= capacity; w++) {// 当前物品的重量超过了背包的容量，不能放入背包if (weights[i-1] > w) {dp[i][w] = dp[i-1][w];  // 不选择当前物品} else {// 选择放入当前物品或不放入当前物品dp[i][w] = Math.max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]]);}}}// 最终返回背包容量为capacity时，能够获得的最大价值return dp[n][capacity];}public static void main(String[] args) {// 物品的重量数组int[] weights = {2, 3, 4, 5};// 物品的价值数组int[] values = {3, 4, 5, 6};// 背包的容量int capacity = 5;// 计算并输出0-1背包问题的最大价值System.out.println("0-1背包最大价值: " + knapsack(weights, values, capacity)); // 输出7}
}

knapsack函数：

• 这个函数使用动态规划来解决 0-1 背包问题。输入参数是物品的重量数组 weights、物品的价值数组 values 和背包的最大容量 capacity。

• dp[i][w]表示考虑前 i 个物品时，在背包容量为 w 时的最大价值。

  对每一个物品 i 和每一个背包容量 w，通过选择是否将当前物品放入背包来更新 dp[i][w]。

  • 如果当前物品的重量大于背包的剩余容量 w，那么不能放入该物品，此时 dp[i][w] = dp[i-1][w]。

  • 如果当前物品的重量不大于背包容量 w

    ，那么我们需要选择将该物品放入背包还是不放入：

    • 不放入：dp[i][w] = dp[i-1][w]
    • 放入：dp[i][w] = values[i-1] + dp[i-1][w - weights[i-1]]，即将该物品放入背包并加上该物品的价值。

  • 选择放入或不放入时，选择较大的那个值

  1. main函数：
     • 定义了一个物品的重量数组 weights，物品的价值数组 values，以及背包的容量 capacity。
     • 调用 knapsack 函数来计算在给定背包容量下，能够获得的最大价值，并输出结果。

  输出：

  当运行时，程序会输出：

  0-1背包最大价值: 7
  

  解释：

  在这个例子中，有四个物品，分别具有以下重量和价值：

  • 物品1：重量=2，价值=3
  • 物品2：重量=3，价值=4
  • 物品3：重量=4，价值=5
  • 物品4：重量=5，价值=6

  背包的容量为5。通过动态规划计算得出最大能够获得的价值为7。选择的物品是：

  • 物品1（重量2，价值3）
  • 物品2（重量3，价值4） 总价值为3 + 4 = 7。

  时间复杂度：

  该算法的时间复杂度为 O(n * capacity)，其中 n 是物品的数量，capacity 是背包的容量。这个复杂度适用于解决中等规模的背包问题。

  空间复杂度：

  空间复杂度为 O(n * capacity)，用于存储 dp 数组的状态。

  3. 贪心算法 (Greedy Algorithm)

  ** 核心思想**

  • 局部最优导向全局最优：每一步选择当前最优解（无需考虑整体）
  • 适用场景：问题满足贪心选择性质和最优子结构（如活动选择、哈夫曼编码）

  典型应用

  • Dijkstra最短路径算法
  • 霍夫曼编码
  • 活动选择问题

  贪心算法（活动选择问题）

  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Comparator;public class GreedyAlgorithm {// 活动选择问题的贪心算法public static ArrayList<int[]> activitySelection(int[] start, int[] end) {int n = start.length; // 获取活动的数量int[][] activities = new int[n][2]; // 创建一个二维数组来存储每个活动的开始时间和结束时间// 将活动的开始时间和结束时间存储到二维数组中for (int i = 0; i < n; i++) {activities[i][0] = start[i];activities[i][1] = end[i];}// 按照活动的结束时间对活动进行排序（从小到大）Arrays.sort(activities, Comparator.comparingInt(a -> a[1])); // 按结束时间排序// 存储选择的活动ArrayList<int[]> selected = new ArrayList<>();// 将第一个活动加入到选择的列表中selected.add(activities[0]);// 记录上一个被选择活动的结束时间int lastEnd = activities[0][1];// 从第二个活动开始检查for (int i = 1; i < n; i++) {// 如果当前活动的开始时间大于上一个活动的结束时间if (activities[i][0] > lastEnd) {// 选择当前活动selected.add(activities[i]);// 更新上一个活动的结束时间为当前活动的结束时间lastEnd = activities[i][1];}}// 返回所有选择的活动return selected;}public static void main(String[] args) {// 活动的开始时间int[] start = {1, 3, 0, 5, 8, 5};// 活动的结束时间int[] end = {2, 4, 6, 7, 9, 9};// 调用活动选择函数，得到所有选择的活动ArrayList<int[]> result = activitySelection(start, end);// 输出选择的活动的时间段System.out.print("选择的活动时间段: ");for (int[] act : result) {System.out.print(Arrays.toString(act) + " ");}// 输出: [1, 2] [3, 4] [5, 7] [8, 9]}
  }

  activitySelection函数：

  • 输入： 活动的开始时间数组 start 和结束时间数组 end。
  • 过程：
    1. 将每个活动的开始时间和结束时间存入二维数组 activities 中。
    2. 按照活动的结束时间对活动进行排序。这里使用了 Arrays.sort() 并通过 Comparator.comparingInt(a -> a[1]) 按照每个活动的结束时间进行升序排列。
    3. 然后从第一个活动开始选择，每次选择一个活动时，只有当当前活动的开始时间大于上一个被选择活动的结束时间时，才能选择当前活动。
    4. 每次选择成功后，更新上一个被选择活动的结束时间，并继续检查下一个活动。
  • 输出： 返回一个 ArrayList，表示被选择的活动。

  main函数：

  • 定义了一个活动的开始时间数组 start 和结束时间数组 end，然后调用 activitySelection 函数计算最优的活动选择。
  • 输出选中的活动时间段。

  输出：

  选择的活动时间段: [1, 2] [3, 4] [5, 7] [8, 9] 

  活动选择过程：

  1. 按结束时间排序后得到的活动顺序：
     • 活动 [1, 2]
     • 活动 [3, 4]
     • 活动 [0, 6]
     • 活动 [5, 7]
     • 活动 [8, 9]
     • 活动 [5, 9]
  2. 贪心算法按照结束时间从小到大选择：
     • 选择第一个活动 [1, 2]。
     • 选择第二个活动 [3, 4]，因为它的开始时间大于 [1, 2] 的结束时间。
     • 选择第四个活动 [5, 7]，因为它的开始时间大于 [3, 4] 的结束时间。
     • 选择第五个活动 [8, 9]，因为它的开始时间大于 [5, 7] 的结束时间。

  时间复杂度：

  • 排序活动的时间复杂度是 O(n log n)，其中 n 是活动的数量。
  • 遍历活动选择合适活动的时间复杂度是 O(n)。
  • 总体时间复杂度为 O(n log n)。

  空间复杂度：

  • 使用了 O(n) 的空间来存储活动数组 activities 和结果数组 selected，因此空间复杂度为 O(n)。

4. 分支限界法 (Branch and Bound)

核心思想

• 剪枝优化搜索：通过上下界限定搜索空间，优先扩展最有希望的分支
• 适用场景：组合优化问题（如旅行商问题、任务分配）

典型应用

• 旅行商问题（TSP）
• 任务分配问题
• 整数规划

5. 分支限界法（任务分配问题）

import java.util.Arrays;
import java.util.PriorityQueue;public class BranchAndBound {// 内部静态类 Node，表示分支限界法中的状态节点static class Node implements Comparable<Node> {int[] assigned;  // 已分配的任务索引，assigned[i]表示工人i分配的任务int cost;        // 当前路径的成本（已分配工人的总成本）int worker;      // 已分配的工人数量int bound;       // 当前节点的下界（用于剪枝优化）public Node(int[] assigned, int cost, int worker) {this.assigned = Arrays.copyOf(assigned, worker); // 复制数组，避免引用冲突this.cost = cost;this.worker = worker;}// 优先队列根据节点的 bound（下界）排序@Overridepublic int compareTo(Node other) {return Integer.compare(this.bound, other.bound);}}/*** 解决任务分配问题的分支限界算法* @param costMatrix 代价矩阵，costMatrix[worker][job] 表示工人分配任务的成本* @return 最小成本*/public static int assignJobs(int[][] costMatrix) {int n = costMatrix.length;  // 工人和任务的总数PriorityQueue<Node> pq = new PriorityQueue<>(); // 优先队列（按bound升序排列）pq.add(new Node(new int[0], 0, 0));int minCost = Integer.MAX_VALUE;// 主循环处理队列中的节点while (!pq.isEmpty()) {Node node = pq.poll(); // 取出当前最优（下界最小）的节点// 如果所有工人都已分配任务，更新最小成本if (node.worker == n) {if (node.cost < minCost) {minCost = node.cost;}continue;}// 尝试为当前工人（node.worker）分配每一个可能的任务for (int job = 0; job < n; job++) {// 检查该任务是否已分配给其他工人if (isJobFree(node.assigned, job)) {// 创建新的分配数组，将当前工人的任务添加到尾部int[] newAssigned = Arrays.copyOf(node.assigned, node.worker + 1);newAssigned[node.worker] = job;// 计算新的总成本（历史成本 + 当前工人执行任务的成本）int newCost = node.cost + costMatrix[node.worker][job];// 创建新节点（worker数量+1）Node nextNode = new Node(newAssigned, newCost, node.worker + 1);// 计算当前新节点的下界（剪枝判断依据）nextNode.bound = calculateBound(nextNode, costMatrix);// 如果下界小于当前已知最小成本，才继续扩展if (nextNode.bound < minCost) {pq.add(nextNode);}}}}return minCost;}/*** 检查任务是否未被分配* @param assigned 已分配的任务数组* @param job      待检测的任务索引* @return 如果任务未被分配则返回 true*/private static boolean isJobFree(int[] assigned, int job) {for (int j : assigned) {if (j == job) return false;}return true;}/*** 计算节点的下界（包含已确定成本和剩余节点的最小可能成本）* 改进后的逻辑：剩余每个工人选择其未分配任务的最小成本之和*/private static int calculateBound(Node node, int[][] costMatrix) {int bound = node.cost;  // 起始值为当前已确定的成本int n = costMatrix.length;// 遍历未分配的工人for (int w = node.worker; w < n; w++) {int minJobCost = Integer.MAX_VALUE;// 遍历所有任务，检查是否未被分配for (int j = 0; j < n; j++) {if (isJobFree(node.assigned, j)) {if (costMatrix[w][j] < minJobCost) {minJobCost = costMatrix[w][j];}}}if (minJobCost != Integer.MAX_VALUE) {bound += minJobCost; // 累加每个未分配工人的最小可能成本}}return bound;}public static void main(String[] args) {int[][] costMatrix = {{9, 2, 7, 8},{6, 4, 3, 7},{5, 8, 1, 8},{7, 6, 9, 4}};int result = assignJobs(costMatrix);System.out.println("最小任务分配成本: " + result); // 正确输出13}
}

输入代价矩阵:
Worker\Task | Task0 | Task1 | Task2 | Task3
---------------------------------------------
Worker0     |   9   |   2   |   7   |   8   
Worker1     |   6   |   4   |   3   |   7   
Worker2     |   5   |   8   |   1   |   8   
Worker3     |   7   |   6   |   9   |   4   最优路径（红色标记）：
Worker0 → Task1（成本2）
Worker1 → Task2（成本3）
Worker2 → Task2（成本1）※ 该任务已被分配 → 实际选择 Task2 → 发生冲突，说明逻辑需要递归剪枝调整
Worker3 → Task3（成本4）总和：2 + 3 + 1 + 4 =  ※ 但正确解应由：
Worker0→Task1(2), Worker1→Task2(3), Worker2→Task2(此处冲突需纠正), 实际正确分配方案为 Worker0→Task1(2), Worker1→Task0(6), Worker2→Task2(1), Worker3→Task3(4)，总成本13

代码运行结果

最小任务分配成本: 13

5. 搜索+回溯算法 (Backtracking)

核心思想

• 试探性搜索：递归探索所有可能性，发现不可行时及时回溯
• 适用场景：组合问题、迷宫问题、N皇后问题、数独

典型应用

• 八皇后问题
• 全排列问题
• 数独求解

4. 回溯算法（N皇后问题

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Backtracking {/*** 解决N皇后问题的入口方法* @param n 棋盘大小(N x N)* @return 所有合法解的集合（每个解表示为一个字符串列表）*/public static List<List<String>> solveNQueens(int n) {List<List<String>> solutions = new ArrayList<>();// 初始化棋盘，'.'表示空位，'Q'表示皇后char[][] board = new char[n][n];for (int i = 0; i < n; i++) {Arrays.fill(board[i], '.'); // 填充每行为空行}backtrack(board, 0, solutions); // 从第0行开始递归return solutions;}/*** 核心回溯方法* @param board 当前棋盘状态* @param row 当前处理的行* @param solutions 存储所有解的结果集*/private static void backtrack(char[][] board, int row, List<List<String>> solutions) {// 终止条件：所有行均已放置皇后if (row == board.length) {solutions.add(formatBoard(board)); // 将当前解保存return;}// 尝试在当前行的每一列放置皇后for (int col = 0; col < board.length; col++) {if (isValid(board, row, col)) {  // 检查当前位置是否合法board[row][col] = 'Q';backtrack(board, row + 1, solutions);  // 递归处理下一行board[row][col] = '.';  // ★ 回溯：撤销当前选择 ★}}}/*** 验证在(row, col)位置放置皇后是否合法* 检查规则：同列无Q，45度/135度对角线上无Q*/private static boolean isValid(char[][] board, int row, int col) {// 遍历检查当前列及对角线（只需检查上方已放置的行）for (int i = 0; i < row; i++) {// 检查同一列是否已有皇后if (board[i][col] == 'Q') return false;int diff = row - i;  // 行差（当前行row与历史行i的差）// 检查左上对角线（列差与行差相等则为对角线）if (col - diff >= 0 && board[i][col - diff] == 'Q') return false;// 检查右上对角线（同上原理）if (col + diff < board.length && board[i][col + diff] == 'Q') return false;}return true;}/*** 将棋盘转换为字符串列表形式* 例如：["..Q.", "Q...", "...Q", ".Q.."]*/private static List<String> formatBoard(char[][] board) {List<String> formatted = new ArrayList<>();for (char[] row : board) {formatted.add(new String(row)); // 将每一行char[]转为字符串}return formatted;}public static void main(String[] args) {int n = 4;List<List<String>> solutions = solveNQueens(n);System.out.println(n + "皇后问题的解法数量: " + solutions.size());  // 输出2// 打印解示例for (List<String> solution : solutions) {System.out.println("\n解法示例：");for (String row : solution) {System.out.println(row);}}}
}

代码运行结果

4皇后问题的解法数量: 2解法示例：
.Q..
...Q
Q...
..Q.解法示例：
..Q.
Q...
...Q
.Q..

回溯的关键操作
当某行所有位置都尝试失败后，函数返回上一行，并撤销上一步的选择
（即board[row][col] = '.'的操作）

时间复杂度分析

• 最坏情况：O(n! * n²)，其中n是棋盘大小
  （遍历所有排列组合，每个验证检查消耗O(n)时间）
• 实际运行：通过及时剪枝（提前发现非法位置），大大减少搜索空间

五大核心算法构建了计算机问题求解的立体框架，每种方法都对应着独特的思维范式与应用场景：

方法论维度

• 分治算法体现模块化解构的哲学，通过递归拆分实现化繁为简
• 动态规划以空间换时间，通过状态转移方程构建结构性记忆
• 贪心算法专注当下最优决策，以局部最优构造全局近似解
• 分支界限法建立智能搜索树，通过剪枝优化遍历效率
• 回溯算法采用试错机制，利用状态重置探索解空间

t.println(“\n解法示例：”);
for (String row : solution) {
System.out.println(row);
}
}
}
}

代码运行结果```java
4皇后问题的解法数量: 2解法示例：
.Q..
...Q
Q...
..Q.解法示例：
..Q.
Q...
...Q
.Q..

回溯的关键操作
当某行所有位置都尝试失败后，函数返回上一行，并撤销上一步的选择
（即board[row][col] = '.'的操作）

时间复杂度分析

• 最坏情况：O(n! * n²)，其中n是棋盘大小
  （遍历所有排列组合，每个验证检查消耗O(n)时间）
• 实际运行：通过及时剪枝（提前发现非法位置），大大减少搜索空间

五大核心算法构建了计算机问题求解的立体框架，每种方法都对应着独特的思维范式与应用场景：

方法论维度

• 分治算法体现模块化解构的哲学，通过递归拆分实现化繁为简
• 动态规划以空间换时间，通过状态转移方程构建结构性记忆
• 贪心算法专注当下最优决策，以局部最优构造全局近似解
• 分支界限法建立智能搜索树，通过剪枝优化遍历效率
• 回溯算法采用试错机制，利用状态重置探索解空间

工程实践中通常复合使用多种算法，例如在回溯框架内结合贪心剪枝策略，或在动态规划中融合分治思想。理解各算法的本质联系与演进关系（如动态规划实质是分治+备忘录的进化形态），才能针对具体问题设计出兼顾时间效率和实现复杂度的混合解法。建议通过LeetCode等算法平台进行组合训练，培养敏锐的算法嗅觉与方案决策能力。