程序员必须知道的核心算法思想

程序员必须掌握的核心算法思想

算法思想 ≠ 代码实现。同一个思想可以用多种语言、多种方式来实现。掌握算法思想，就是掌握问题求解的本质，通过不同的实现方式，将问题解决得更加高效。

概述

算法是解决问题的方法，解决问题的方法离不开指导思想，指导思想是解决问题的关键。
作为程序员，当我们面对一个复杂问题时，最重要的不是立刻敲代码，而是选对解题的思路。
本指南介绍了5种核心算法思想 + 2种常见问题解决策略。这些思想和策略贯穿于整个计算机编程领域，掌握它们将让你的编程能力有质的飞跃。
有哪些算法思想？

1. 贪心（Greedy）

定义：即在每个决策点，都选择当下局部最优的选择，期望通过一系列局部最优决策来得到全局的最优解。简单讲就是步步最优，最终得到全局最优。贪心算法广泛应用于优化问题，如最短路径、背包问题、矩阵链乘法等。
核心特性：

• 贪心选择性质：全局最优解可由局部最优选择导出
  
• 最优子结构：原问题的最优解包含其子问题的最优解
  

算法流程：

1. 初始问题 → 选择局部最优 → 更新问题状态 → 重复 → 最终解

复制代码

伪代码：

1. Algorithm Greedy(Problem P):
2.     solution = ∅
3.     while P is not fully solved:
4.         // 局部最优选择，最后会得到全局最优解
5.         choice = selectBestChoice(P)
6.         solution = solution + choice
7.         // 更新问题状态, 准备下一次选择
8.         P = reducedProblem(P, choice)
9.     return solution

复制代码

适用条件：

• 问题具有贪心选择性质和最优子结构
  
• 不能回溯或修改已做的选择
  

典型应用：

• 分数背包：按单位价值从高到低选择物品
  
• 最小生成树：Kruskal（边贪心）、Prim（顶点贪心）
  
• 最短路径：Dijkstra 算法
  
• 哈夫曼编码：频率最低的两个节点合并
  
• 活动选择：选择最早结束的活动
  

2. 分治（Divide and Conquer）

定义：将原始问题分解为若干个规模更小、结构相同的子问题，通过递归式逐步求解各子问题，然后合并子问题的解以得到原始问题的解。简单理解就是以大化小，分而治之。分治算法广泛应用于排序、查找、矩阵运算等问题。
三个关键步骤：

• Divide（分）：将问题分解为独立的子问题
  
• Conquer（治）：递归求解子问题
  
• Combine（合）：合并子问题的解
  

算法流程：

1. 初始问题 → 分解 → 递归求解子问题 → 合并子问题解 → 最终解

复制代码

伪代码：

1. Algorithm DivideConquer(Problem P, boundary b):
2.     // 基础情况
3.     if P.size <= b:                    
4.         return directSolve(P)
5.    
6.     // 分解, 子问题相互独立
7.     subProblems = divide(P)
8.    
9.     // 递归求解, 合并子问题解
10.     subSolutions = []
11.     for each subProblem in subProblems:
12.         subSolutions.add(DivideConquer(subProblem, b))
13.    
14.     // 合并子问题解
15.     return combine(subSolutions)

复制代码

分支策略：

• 深度优先分支（DFS）：通常与剪枝结合，内存效率高
  
• 广度优先分支（BFS）：更快到达最优解
  
• 最优优先分支：每次选择界最小的节点，收敛快
  

适用条件：

• 问题是最优化问题（求最大值或最小值）
  
• 能够快速计算界（下界或上界）
  
• 界的计算不能过于复杂
  

典型应用：

• 旅行商问题（TSP）：利用矩阵规化的下界
  
• 0-1 背包最优化版：分数背包放松的上界
  
• 任务分配：利用最小费用匹配的下界
  
• 装箱问题：利用物品总体积的下界
  
• 作业调度：利用关键路径的下界
  

二、搜索策略

搜索策略不算是核心算法思想，而是一种解决问题的策略。它定义了在状态空间中如何系统地探索节点，以找到目标状态或满足特定条件的解。搜索策略可以分为两大类：深度优先搜索（DFS）和广度优先搜索（BFS）。
6. 搜索（Search）

定义：搜索就是在状态空间中系统性地探索节点，从初始状态逐步转移到目标状态，或在所有可达状态中寻找特定目标。简单说就是按照某种策略（如广度优先、深度优先）遍历状态节点，直到找到目标或遍历完所有节点。搜索策略广泛应用于路径查找、状态空间探索等问题。
广度优先搜索（BFS）

特点：广度优先搜索是一种按层遍历的搜索策略，逐层扩展，先扩展距起点近的节点。一般通过队列实现，确保先访问距离起点近的节点。
实现原理：

1.         原问题
2.        /  |  \
3.       /   |   \
4. 子问题1   2    3
5.     /|    |    | \
6.    ...   ...   ...

复制代码

遍历原理：

1.      DP[1]        DP[2]        DP[3]  ...  DP[n]
2.       ↑            ↑            ↑            ↑
3.       └────────────┴────────────┴────────────┘
4.                 状态转移方程链

复制代码

特性：

• 完备性：若目标存在必定找到
  
• 最优性：在无权图中找到最短路径
  
• 空间复杂度：O(b^d)，b 为分支因子，d 为深度
  

应用：无权最短路径、连通性检测、层级遍历
深度优先搜索（DFS）

特点：深度优先搜索是一种沿一条路走到底，再回溯尝试其他路径的搜索策略。简单来说就是先从一条路走到底，然后回溯到上一个节点，从另一条路走到底。它通常用栈或递归实现。
实现原理 - 递归版：

1. Algorithm DP_Tabulation(Problem P, int n):
2.     // 创建 DP 表
3.     dp[0...n] = new Array
4.    
5.     // 初始化边界条件
6.     dp[0] = baseCase()
7.    
8.     // 逐步填表，填充 dp[i]
9.     for i = 1 to n:
10.         for j = 0 to i-1:  // 可能的状态转移
11.             dp[i] = max/min(dp[i], transitionFunc(dp[j], ...))
12.    
13.     return dp[n]

复制代码

实现原理 - 迭代版（栈）：

1. HashMap<State, Value> memo = new HashMap()
3. Algorithm DP_Memoization(State s):
4.     if s in memo:
5.         return memo[s]
6.     // 递归求解子问题
7.     if isBase(s):
8.         return baseValue(s)
9.    
10.     // 递归求解并存储
11.     result = transitionFunc(subStates)
12.     memo[s] = result
13.     return result

复制代码

遍历顺序：

1.               根节点
2.             /   |   \
3.           分支1 分支2 分支3
4.          /  |   |   |
5.        ...剪枝 ...剪枝...

复制代码

应用：拓扑排序、强连通分量、回溯搜索、括号生成
启发式搜索（A*）

特点： 启发式搜索是一类利用启发函数评估节点潜力的搜索策略，其中典型算法是 A*（A-star）搜索。
核心思想是通过启发函数 f(n) = g(n) + h(n) 评估每个节点的优先级，其中 g(n) 表示从起点到当前节点的实际代价，h(n) 表示从当前节点到目标节点的估计代价。算法优先扩展 f(n) 最小、最有希望到达目标的节点。
概念解析：

• g(n)：从起点到当前节点 n 的实际代价
  
• h(n)：启发估计，从 n 到目标的估计代价（需满足可采纳性）
  
• f(n)：整体估计，决定节点优先级（越小越优先）
  

算法图例：

1. Algorithm Backtracking(candidates, track, constraints):
2.     // 完成一个合法方案
3.     if isSolution(track, constraints):
4.         solutions.add(copy(track))
5.         return
7.     // 剪枝：路径已不满足约束
8.     if !isValid(track, constraints):
9.         return
11.     // 选择、探索、撤销（Choose-Explore-Unchoose）
12.     for choice in candidates:
13.         track.add(choice)                       // 选择
14.         Backtracking(rest, track, constraints)  // 探索
15.         track.remove(choice)                    // 撤销

复制代码

伪代码：

1.        节点
2.        / │ \
3.       /  │  \
4.     节点2   节点3 ...
5.     ↓    ↓    ↓
6.     界   界   界  ← 每个分支的下界
7.     ↓    ↓
8.   比较当前最优值，决定是否剪枝

复制代码

启发函数设计：

• 曼哈顿距离（h(n) = |x₁-x₂| + |y₁-y₂|）：网格问题
  
• 欧几里得距离（h(n) = √((x₁-x₂)² + (y₁-y₂)²)）：连续空间
  
• 直线距离：任何空间
  

可采纳性条件：h(n) ≤ 实际最小代价，保证找到最优解
应用：游戏 AI 寻路、机器人导航、地图导航
迭代加深（IDDFS）

特点：迭代加深搜索（IDDFS）结合了 深度优先搜索（DFS） 的低空间消耗和 广度优先搜索（BFS） 的逐层搜索特性，通过逐步增加搜索深度限制，重复进行深度优先搜索，直到找到目标节点。核心思想是从深度 0 开始进行深度优先搜索，每次将最大搜索深度增加 1，逐层扩展搜索范围，从而在保证较低空间复杂度的同时找到最浅层的解。
实现原理：

1. Algorithm BranchAndBound(initialState, costFunc):
2.     bestValue = ∞  // 当前最优解的值
3.     bestSolution = null
4.     queue = PriorityQueue()  // 按下界排序
5.     queue.push(initialState, 0)
6.    
7.     while queue is not empty:
8.         node = queue.pop()  // 取界最小的节点
9.         
10.         // 剪枝：界超过当前最优
11.         if lowerBound(node) >= bestValue:
12.             continue
13.         
14.         // 找到完全解
15.         if isComplete(node):
16.             if cost(node) < bestValue:
17.                 bestValue = cost(node)
18.                 bestSolution = node
19.         else:
20.             // 生成子节点并入队
21.             for child in branch(node):
22.                 if lowerBound(child) < bestValue:
23.                     queue.push(child, lowerBound(child))
24.    
25.     return bestSolution

复制代码

深度限制 DFS：

1. Algorithm BFS(Graph G, start, target):
2.     queue = Queue()
3.     visited = Set()
4.     queue.enqueue(start)
5.     visited.add(start)
6.     // 从队列中取出节点，检查是否为目标节点
7.     while queue is not empty:
8.         node = queue.dequeue()
9.         if node == target:
10.             return found(node)
11.         // 遍历当前节点的所有邻居
12.         for neighbor in G.getNeighbors(node):
13.             if neighbor not in visited:
14.                 visited.add(neighbor)
15.                 queue.enqueue(neighbor)
16.    
17.     return notFound()

复制代码

搜索轨迹：

1.        起点
2.       / | \
3.      1  2  3   ← 第 1 层
4.     /| |\ |    ← 第 2 层
5.    ...   ...  ...

复制代码

特性：

• 空间复杂度：O(d)，d 为解的深度（DFS 优势）
  
• 时间复杂度：O(b^d)，与 BFS 相同但常数因子更小
  
• 应用：深度未知的大规模搜索空间
  

搜索策略对比表：
策略完备性最优性时间空间适用场景BFS✓✓（无权）O(b^d)O(b^d)无权、层级DFS✓✗O(b^d)O(d)内存受限、回溯A*✓✓（可采纳h）依赖h依赖h启发式、寻路IDDFS✓✓（无权）O(b^d)O(d)unknown depth三、随机化算法

7. 随机化（Randomization）

随机化不算是核心算法思想，而是一种解决问题的策略。
定义：随机化在算法的执行过程中引入随机性（通常是随机选择），以期望意义上改进性能、打破对手的最坏情况构造、简化问题分析。简单来说就是在算法中引入随机因素。
随机化用到的地方很多，比如在排序算法中，随机选择枢轴（pivot）可以避免最坏情况的发生；在图算法中，随机化可以用于快速逼近最短路径；在机器学习中，随机化可以用于初始化模型参数等。
理论基础：

• 随机变量期望：E[X] = Σ probability(x) × value(x)
  
• 高概率事件：事件发生概率至少为 1 - δ（δ 很小）
  
• 几何分布：第一次成功的期望次数
  

两大类型：
蒙特卡洛算法（Monte Carlo）

特点：

• 运行时间固定或确定
  
• 结果可能有误差概率
  
• 错误是可控的（通过多次运行降低误差率）
  

伪代码：

1. Algorithm DFS_Recursive(node, target, visited, Graph G):
2.     if node == target:
3.         return found(node)
4.    
5.     visited.add(node)
6.     // 遍历当前节点的所有邻居
7.     for neighbor in G.getNeighbors(node):
8.         if neighbor not in visited:
9.             // 递归调用 DFS 搜索邻居
10.             result = DFS_Recursive(neighbor, target, visited, G)
11.             if result found:
12.                 return result
13.    
14.     return notFound()

复制代码

误差率分析：

1. Algorithm DFS_Iterative(start, target, Graph G):
2.     stack = Stack()
3.     visited = Set()
4.     stack.push(start)
5.     visited.add(start)
6.     // 从栈中弹出节点，检查是否为目标节点
7.     while stack is not empty:
8.         node = stack.pop()
9.         if node == target:
10.             return found(node)
11.         // 遍历当前节点的所有邻居
12.         for neighbor in G.getNeighbors(node):
13.             if neighbor not in visited:
14.                 visited.add(neighbor)
15.                 stack.push(neighbor)
16.    
17.     return notFound()

复制代码

典型应用：

• 蒙特卡洛估算圆周率：随机点落在圆内的比例
  
• 概率验证：检验某个数是否素数（Miller-Rabin）
  
• 数值积分：随机采样点估算函数积分
  
• 随机采样：大规模数据中的无偏采样
  

拉斯维加斯算法（Las Vegas）

特点：

• 结果一定正确
  
• 运行时间具有随机性
  
• 性能是概率意义上的
  

伪代码：

1.     起点
2.     │
3.     ├─→ 1-1-1-1  ← 一条路走到底
4.     │
5.     └─→ 2-2-2    ← 回溯再走另一条路

复制代码

时间复杂度分析：

1.          起点
2.          / │ \
3.         /  │  \
4.      节点1 节点2 节点3
5.      (f=10) (f=5) (f=8)

复制代码

典型应用：

• 随机快速排序：随机选择枢轴，平均时间 O(n log n)
  
• 跳表：随机化的平衡链表，支持 O(log n) 搜索
  
• 哈希表：随机哈希函数减少碰撞
  
• 素数测试：随机见证人验证（Miller-Rabin）
  
• 随机最小割：Karger 的最小割算法
  

算法对比：
维度蒙特卡洛拉斯维加斯结果正确性可能有误差一定正确时间复杂度确定性或固定随机的，需期望分析失败处理多次运行取多数失败重试应用倾向检验、估算、模拟快速查找、排序选择指南：

• 若答案必须正确且有高效验证方式：选 Las Vegas
  
• 若单次答案可接受误差但需快速得到估计：选 Monte Carlo
  
• 若需完全可靠但允许长时间运行：Las Vegas 多次运行
  
• 若需快速近似不在乎偶现错误：Monte Carlo + 验证
  

总结

算法思想是解决问题的核心，掌握了这些基本的算法思想，就掌握了问题求解的本质。
无论是贪心、分治、动态规划、回溯、分支定界，还是搜索策略和随机化算法，理解和应用这些算法思想，你将能够更高效地设计和实现各种复杂问题的解决方案。
算法思想+策略对比表

思想定义适用条件典型应用贪心每一步选择局部最优贪心选择性质 + 最优子结构分数背包、最小生成树、最短路径、哈夫曼编码、活动选择分治分解为相同的小问题，递归求解，合并结果子问题相互独立、结构相同、可高效合并归并排序、快速排序、二分查找、矩阵乘法、凸包、逆序对计数动态规划识别重叠子问题，用空间换时间避免重复计算存在重叠子问题、最优子结构（无后效性）背包问题、最长递增子序列、最长公共子序列、编辑距离、矩阵路径和、爬楼梯、硬币兑换回溯逐个尝试所有选择，发现路走不通时回退重试需要枚举所有可能、有树形/递归结构、存在约束条件全排列、组合、子集、八皇后问题、数独求解、岛屿数量、迷宫寻路、电话号码字母组合分支定界在回溯基础上，为每个节点计算界，实现更优剪枝优化问题、能快速计算界的条件旅行商问题、0-1背包最优化版、任务分配、装箱问题、作业调度搜索在状态空间中系统性探索，从初始状态转移到目标状态问题具有状态转移特征、能定义目标状态无权最短路径、连通性检测、层级遍历、拓扑排序、强连通分量、游戏AI寻路随机化在算法中引入随机性，改进性能或简化分析需要打破最坏情况、可接受概率保证随机快速排序、跳表、哈希表、Miller-Rabin素数测试、最小割算法源码

• 算法实现源码：https://github.com/microwind/algorithms/
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！