第二十六 算法
算法（Algorithm）是解决特定问题的一系列明确、有限的计算步骤。如果说编程语言是工具，那么算法就是使用这些工具的方法论。好的算法能够在有限的时间和空间内，高效地解决问题。
一、算法基础
1.1 什么是算法
算法具有五个基本特性：
| 特性 | 说明 |
|---|---|
| 有穷性 | 算法必须在有限步骤后结束 |
| 确定性 | 每一步都有明确的定义，无二义性 |
| 可行性 | 每一步都可以通过基本运算实现 |
| 输入 | 有零个或多个输入 |
| 输出 | 至少有一个输出 |
1.2 算法效率的度量
评价算法好坏的核心指标是时间复杂度和空间复杂度。
大 O 记号（Big-O Notation）
大 O 记号描述算法运行时间随输入规模增长的趋势：
| 复杂度 | 记号 | 说明 | 示例 |
|---|---|---|---|
| 常数时间 | O(1) | 与输入规模无关 | 数组按索引访问 |
| 对数时间 | O(log n) | 每步将问题规模减半 | 二分查找 |
| 线性时间 | O(n) | 与输入规模成正比 | 遍历数组 |
| 线性对数 | O(n log n) | 线性乘以对数 | 归并排序、快速排序 |
| 平方时间 | O(n²) | 双重循环 | 冒泡排序 |
| 指数时间 | O(2ⁿ) | 每步问题规模翻倍 | 穷举子集 |
| 阶乘时间 | O(n!) | 全排列 | 旅行商问题（暴力） |
#![allow(unused)]
fn main() {
// O(1) - 常数时间
fn get_first(arr: &[i32]) -> Option<i32> {
arr.first().copied() // 直接访问，与数组长度无关
}
// O(n) - 线性时间
fn find_max(arr: &[i32]) -> Option<i32> {
arr.iter().max().copied() // 需要遍历整个数组
}
// O(n²) - 平方时间
fn bubble_sort(arr: &mut [i32]) {
let n = arr.len();
for i in 0..n {
for j in 0..n - i - 1 {
if arr[j] > arr[j + 1] {
arr.swap(j, j + 1);
}
}
}
}
}复杂度比较（n = 1000 时）：
| 复杂度 | 操作次数 |
|---|---|
| O(1) | 1 |
| O(log n) | ~10 |
| O(n) | 1,000 |
| O(n log n) | ~10,000 |
| O(n²) | 1,000,000 |
| O(2ⁿ) | 约 10³⁰¹ |
当 n 很大时，算法复杂度的差异会变得极其显著。O(n²) 算法处理 10⁶ 数据可能需要数小时，而 O(n log n) 算法只需数秒。
二、算法思想
2.1 枚举法（Brute Force）
枚举法是最直接的算法思想：遍历所有可能的情况，逐一验证是否满足条件。
// 例：找出 1~100 中的所有素数
fn find_primes(limit: u32) -> Vec<u32> {
let mut primes = Vec::new();
for n in 2..=limit {
let mut is_prime = true;
for i in 2..n {
if n % i == 0 {
is_prime = false;
break;
}
}
if is_prime {
primes.push(n);
}
}
primes
}
fn main() {
println!("{:?}", find_primes(50));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
}枚举法简单直接，但效率通常不高。上面的素数查找可以优化到 O(n log log n)（埃拉托斯特尼筛法）。
2.2 分治法（Divide and Conquer）
分治法的核心思想：将大问题分解为若干相似的子问题，递归解决子问题，再合并结果。
分治法的三个步骤：
- 分解：将原问题分解为若干子问题
- 解决：递归解决子问题（若子问题足够小，直接求解）
- 合并：将子问题的解合并为原问题的解
// 归并排序（Merge Sort）- 经典分治算法
fn merge_sort(arr: &mut [i32]) {
let len = arr.len();
if len <= 1 {
return;
}
let mid = len / 2;
merge_sort(&mut arr[..mid]);
merge_sort(&mut arr[mid..]);
// 合并两个有序数组
let mut temp = arr.to_vec();
merge(&arr[..mid], &arr[mid..], &mut temp);
arr.copy_from_slice(&temp);
}
fn merge(left: &[i32], right: &[i32], result: &mut [i32]) {
let (mut i, mut j, mut k) = (0, 0, 0);
while i < left.len() && j < right.len() {
if left[i] <= right[j] {
result[k] = left[i];
i += 1;
} else {
result[k] = right[j];
j += 1;
}
k += 1;
}
while i < left.len() {
result[k] = left[i];
i += 1;
k += 1;
}
while j < right.len() {
result[k] = right[j];
j += 1;
k += 1;
}
}
fn main() {
let mut arr = [38, 27, 43, 3, 9, 82, 10];
merge_sort(&mut arr);
println!("{:?}", arr); // [3, 9, 10, 27, 38, 43, 82]
}时间复杂度分析： 归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)。
2.3 动态规划（Dynamic Programming）
动态规划（DP）的核心思想：将问题分解为重叠子问题，存储子问题的解以避免重复计算。
DP 的两个关键要素：
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：子问题会被重复计算多次
// 斐波那契数列 - 动态规划解法
fn fib_dp(n: u32) -> u64 {
if n == 0 { return 0; }
if n == 1 { return 1; }
let mut dp = vec![0u64; (n + 1) as usize];
dp[1] = 1;
for i in 2..=n as usize {
dp[i] = dp[i - 1] + dp[i - 2];
}
dp[n as usize]
}
// 空间优化版 - 只保留前两个状态
fn fib_dp_optimized(n: u32) -> u64 {
if n == 0 { return 0; }
if n == 1 { return 1; }
let (mut prev, mut curr) = (0u64, 1u64);
for _ in 2..=n {
let next = prev + curr;
prev = curr;
curr = next;
}
curr
}
fn main() {
println!("F(50) = {}", fib_dp(50)); // 12586269025
println!("F(50) = {}", fib_dp_optimized(50)); // 12586269025
}经典问题：0/1 背包问题
// 0/1 背包问题
// 有 n 个物品，每个物品有重量 weight[i] 和价值 value[i]
// 背包容量为 W，求能装入的最大价值
fn knapsack(weights: &[usize], values: &[usize], capacity: usize) -> usize {
let n = weights.len();
let mut dp = vec![vec![0; capacity + 1]; n + 1];
for i in 1..=n {
for w in 0..=capacity {
if weights[i - 1] <= w {
// 可以选择放入或不放入
dp[i][w] = dp[i - 1][w].max(
dp[i - 1][w - weights[i - 1]] + values[i - 1]
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
dp[n][capacity]
}
fn main() {
let weights = vec![2, 3, 4, 5];
let values = vec![3, 4, 5, 6];
let capacity = 8;
println!("最大价值: {}", knapsack(&weights, &values, capacity)); // 10
}时间复杂度： O(n × W)，其中 n 是物品数量，W 是背包容量。
2.4 贪心算法（Greedy Algorithm）
贪心算法的核心思想：每一步都做出当前看起来最优的选择，希望最终得到全局最优解。
贪心算法不一定能得到全局最优解，但在某些问题上是有效的。
// 找零钱问题（贪心解法）
// 假设硬币面额为 1, 5, 10, 25, 50
fn make_change(amount: usize) -> Vec<usize> {
let coins = vec![50, 25, 10, 5, 1];
let mut change = Vec::new();
let mut remaining = amount;
for &coin in &coins {
while remaining >= coin {
change.push(coin);
remaining -= coin;
}
}
change
}
fn main() {
let amount = 87;
let change = make_change(amount);
println!("找 {} 分钱: {:?}", amount, change);
// 找 87 分钱: [50, 25, 10, 1, 1]
println!("硬币数量: {}", change.len()); // 5
}注意： 贪心算法在标准硬币系统（如 1, 5, 10, 25）下能得到最优解，但在某些面额组合（如 1, 3, 4）下可能不是最优。此时需要使用动态规划。
2.5 回溯法（Backtracking）
回溯法的核心思想：系统地搜索问题的解空间，当发现当前路径不可能得到解时，回溯到上一步尝试其他路径。
// 全排列问题
fn permutations(nums: &mut [i32]) -> Vec<Vec<i32>> {
let mut result = Vec::new();
backtrack(nums, 0, &mut result);
result
}
fn backtrack(nums: &mut [i32], start: usize, result: &mut Vec<Vec<i32>>) {
if start == nums.len() {
result.push(nums.to_vec());
return;
}
for i in start..nums.len() {
nums.swap(start, i); // 做选择
backtrack(nums, start + 1, result); // 递归
nums.swap(start, i); // 撤销选择（回溯）
}
}
fn main() {
let mut nums = [1, 2, 3];
let perms = permutations(&mut nums);
for p in &perms {
println!("{:?}", p);
}
// [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]
}三、搜索算法
3.1 深度优先搜索（DFS）
DFS 沿着一条路径尽可能深地搜索，直到无法继续才回溯。
// 图的深度优先搜索
use std::collections::{HashMap, HashSet};
struct Graph {
adj: HashMap<i32, Vec<i32>>,
}
impl Graph {
fn new() -> Self {
Graph { adj: HashMap::new() }
}
fn add_edge(&mut self, u: i32, v: i32) {
self.adj.entry(u).or_insert_with(Vec::new).push(v);
self.adj.entry(v).or_insert_with(Vec::new).push(u);
}
fn dfs(&self, start: i32) -> Vec<i32> {
let mut visited = HashSet::new();
let mut result = Vec::new();
self.dfs_helper(start, &mut visited, &mut result);
result
}
fn dfs_helper(&self, node: i32, visited: &mut HashSet<i32>, result: &mut Vec<i32>) {
visited.insert(node);
result.push(node);
if let Some(neighbors) = self.adj.get(&node) {
for &neighbor in neighbors {
if !visited.contains(&neighbor) {
self.dfs_helper(neighbor, visited, result);
}
}
}
}
}
fn main() {
let mut graph = Graph::new();
graph.add_edge(0, 1);
graph.add_edge(0, 2);
graph.add_edge(1, 3);
graph.add_edge(1, 4);
graph.add_edge(2, 5);
println!("DFS: {:?}", graph.dfs(0)); // [0, 1, 3, 4, 2, 5]
}3.2 广度优先搜索（BFS）
BFS 逐层扩展搜索，先访问所有邻居，再访问邻居的邻居。
// 图的广度优先搜索
use std::collections::{HashMap, HashSet, VecDeque};
struct Graph {
adj: HashMap<i32, Vec<i32>>,
}
impl Graph {
fn new() -> Self {
Graph { adj: HashMap::new() }
}
fn add_edge(&mut self, u: i32, v: i32) {
self.adj.entry(u).or_insert_with(Vec::new).push(v);
self.adj.entry(v).or_insert_with(Vec::new).push(u);
}
fn bfs(&self, start: i32) -> Vec<i32> {
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
let mut result = Vec::new();
visited.insert(start);
queue.push_back(start);
while let Some(node) = queue.pop_front() {
result.push(node);
if let Some(neighbors) = self.adj.get(&node) {
for &neighbor in neighbors {
if !visited.contains(&neighbor) {
visited.insert(neighbor);
queue.push_back(neighbor);
}
}
}
}
result
}
}
fn main() {
let mut graph = Graph::new();
graph.add_edge(0, 1);
graph.add_edge(0, 2);
graph.add_edge(1, 3);
graph.add_edge(1, 4);
graph.add_edge(2, 5);
println!("BFS: {:?}", graph.bfs(0)); // [0, 1, 2, 3, 4, 5]
}DFS vs BFS 对比：
- DFS 使用栈（递归或显式栈），适合寻找路径、拓扑排序
- BFS 使用队列，适合寻找最短路径（无权图）
四、经典排序算法
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 | 特点 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 简单，效率低 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 交换次数少 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 对小数据高效 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 稳定，需额外空间 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 平均最快 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 空间效率高 |
// 快速排序
fn quick_sort(arr: &mut [i32]) {
if arr.len() <= 1 {
return;
}
let pivot_index = partition(arr);
let (left, right) = arr.split_at_mut(pivot_index);
quick_sort(left);
quick_sort(&mut right[1..]);
}
fn partition(arr: &mut [i32]) -> usize {
let len = arr.len();
let pivot = arr[len - 1];
let mut i = 0;
for j in 0..len - 1 {
if arr[j] <= pivot {
arr.swap(i, j);
i += 1;
}
}
arr.swap(i, len - 1);
i
}
fn main() {
let mut arr = [64, 34, 25, 12, 22, 11, 90];
quick_sort(&mut arr);
println!("{:?}", arr); // [11, 12, 22, 25, 34, 64, 90]
}五、经典问题选讲
5.1 八皇后问题
在 8×8 的棋盘上放置 8 个皇后，使它们互不攻击（不在同一行、列、对角线）。
fn solve_n_queens(n: usize) -> Vec<Vec<String>> {
let mut board = vec![vec!['.'; n]; n];
let mut result = Vec::new();
backtrack_queen(&mut board, 0, &mut result);
result
}
fn backtrack_queen(board: &mut Vec<Vec<char>>, row: usize, result: &mut Vec<Vec<String>>) {
let n = board.len();
if row == n {
result.push(board.iter().map(|r| r.iter().collect()).collect());
return;
}
for col in 0..n {
if is_valid(board, row, col) {
board[row][col] = 'Q';
backtrack_queen(board, row + 1, result);
board[row][col] = '.';
}
}
}
fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize) -> bool {
let n = board.len();
// 检查列
for i in 0..row {
if board[i][col] == 'Q' {
return false;
}
}
// 检查左上对角线
for i in 1..=row {
if col >= i && board[row - i][col - i] == 'Q' {
return false;
}
}
// 检查右上对角线
for i in 1..=row {
if col + i < n && board[row - i][col + i] == 'Q' {
return false;
}
}
true
}
fn main() {
let solutions = solve_n_queens(8);
println!("8 皇后问题共有 {} 种解法", solutions.len()); // 92
}5.2 最长公共子序列（LCS）
// 动态规划求解最长公共子序列
fn longest_common_subsequence(text1: &str, text2: &str) -> usize {
let m = text1.len();
let n = text2.len();
let mut dp = vec![vec![0; n + 1]; m + 1];
let chars1: Vec<char> = text1.chars().collect();
let chars2: Vec<char> = text2.chars().collect();
for i in 1..=m {
for j in 1..=n {
if chars1[i - 1] == chars2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
}
}
}
dp[m][n]
}
fn main() {
println!("{}", longest_common_subsequence("ABCDE", "ACE")); // 3 ("ACE")
println!("{}", longest_common_subsequence("ABC", "DEF")); // 0
}六、算法学习资源
| 资源 | 说明 |
|---|---|
| TheAlgorithms | 开源算法库，支持多种编程语言 |
| VisuAlgo | 算法可视化网站，直观理解算法执行过程 |
| LeetCode | 算法练习题库 |
| 3Blue1Brown | 数学与算法的可视化讲解 |
七、总结
| 算法思想 | 核心思想 | 适用场景 | 经典问题 |
|---|---|---|---|
| 枚举 | 遍历所有可能 | 解空间小 | 素数查找 |
| 分治 | 分解、解决、合并 | 可分解为独立子问题 | 归并排序、快速排序 |
| 动态规划 | 存储子问题解 | 最优子结构、重叠子问题 | 背包问题、LCS |
| 贪心 | 局部最优 | 具有贪心选择性质 | 找零钱、活动选择 |
| 回溯 | 深度搜索+剪枝 | 解空间树搜索 | 八皇后、全排列 |
算法是编程的灵魂。掌握这些基本算法思想，能够帮助我们更高效地解决各种计算问题。
练习建议：
- 实现一个二分查找算法
- 用动态规划解决斐波那契数列问题
- 尝试解决 LeetCode 上的经典算法题