分治算法、动态规划、贪心算法、分支限界法和回溯算法的深度对比
1. 分治算法 (Divide and Conquer)
核心思想
- 分治法三步曲：
- 分解（Divide）：将原问题拆分为多个子问题
- 解决（Conquer）：递归解决子问题
- 合并（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));
}
}
主要流程：
mergeSort：主函数，检查数组的有效性，并创建一个临时数组，然后调用递归函数。mergeSort（递归）：将数组分解成更小的部分，直到每个部分只有一个元素。merge：合并两个已排序的子数组，返回一个合并后的排序数组。
归并排序的工作原理：
- 分解：递归将数组不断划分为两个子数组，直到每个子数组的长度为1。
- 合并：通过
merge函数将两个有序的子数组合并成一个更大的有序数组。
输出：
当运行时，程序会打印排序后的数组：
归并排序结果: [1, 2, 3, 4, 5, 6, 7, 8]
时间复杂度：
归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。尽管归并排序的空间复杂度相对较高（O(n)），但它稳定并且适用于大规模数据的排序。
2. 动态规划 (Dynamic Programming)
核心思想
- 递推优化：通过存储子问题的解（记忆化表），避免重复计算
- 适用场景：存在重叠子问题和最优子结构（如最短路径、背包问题）
动态规划两要素
- 状态转移方程（递推公式）
- 边界条件
典型应用
- 斐波那契数列（记忆化优化）
- 0-1背包问题
- 最长公共子序列（LCS）
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]]，即将该物品放入背包并加上该物品的价值。
- 不放入：
-
选择放入或不放入时，选择较大的那个值
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。 - 过程：
- 将每个活动的开始时间和结束时间存入二维数组
activities中。 - 按照活动的结束时间对活动进行排序。这里使用了
Arrays.sort()并通过Comparator.comparingInt(a -> a[1])按照每个活动的结束时间进行升序排列。 - 然后从第一个活动开始选择，每次选择一个活动时，只有当当前活动的开始时间大于上一个被选择活动的结束时间时，才能选择当前活动。
- 每次选择成功后，更新上一个被选择活动的结束时间，并继续检查下一个活动。
- 将每个活动的开始时间和结束时间存入二维数组
- 输出： 返回一个
ArrayList，表示被选择的活动。
main函数：- 定义了一个活动的开始时间数组
start和结束时间数组end，然后调用activitySelection函数计算最优的活动选择。 - 输出选中的活动时间段。
输出：
选择的活动时间段: [1, 2] [3, 4] [5, 7] [8, 9]活动选择过程：
- 按结束时间排序后得到的活动顺序：
- 活动 [1, 2]
- 活动 [3, 4]
- 活动 [0, 6]
- 活动 [5, 7]
- 活动 [8, 9]
- 活动 [5, 9]
- 贪心算法按照结束时间从小到大选择：
- 选择第一个活动 [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）
- 任务分配问题
- 整数规划
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（下界）排序
@Override
public 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皇后问题、数独
典型应用
- 八皇后问题
- 全排列问题
- 数独求解
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等算法平台进行组合训练，培养敏锐的算法嗅觉与方案决策能力。