常见算法与应用
什么是算法？
算法是解决特定问题的一系列步骤或方法。一个好的算法不仅要正确，还应具备较高的效率。
如何评价一个算法？
评价算法的常用指标有：
- 时间复杂度：算法运行所需时间随输入规模变化的增长趋势。
- 空间复杂度：算法执行过程中占用的内存空间随输入规模的变化趋势。
通常采用大 O 记法（Big O Notation）来表示渐近复杂度，即在输入规模足够大的情况下，时间/空间的增长速度。
常见时间复杂度级别及示例
| 时间复杂度 | 示例算法或场景 | 说明 |
|---|---|---|
| O(1) | 哈希查找、布隆过滤器 | 常量时间操作，与输入规模无关 |
| O(log n) | 折半查找（二分查找） | 每次操作将问题规模缩小一半 |
| O(n) | 顺序查找、计数排序 | 线性扫描或遍历每个元素一次 |
| O(n log n) | 快速排序、归并排序、堆排序 | 高效的比较类排序算法 |
| O(n²) | 冒泡排序、选择排序、插入排序 | 两层嵌套循环，适用于小规模数据 |
| O(n³) | Floyd 算法、三重循环的矩阵乘法 | 三层嵌套循环 |
| O(2ⁿ) | 子集枚举、部分回溯算法（如八皇后） | 指数增长，规模略大就难以处理 |
| O(n!) | 全排列、旅行商问题（TSP） | 阶乘级增长，常见于组合爆炸问题，属于 NP 完全问题 |
- O(1)、O(log n)、O(n) 属于高效算法；
- O(n²) 及以上的复杂度，适用于数据量小或可接受较长计算时间的场景；
排序算法
简单选择排序
简单选择排序，它的特点是：
- 每一轮从未排序部分中找出最小值；
- 然后与当前位置交换；
- 每一轮最多只交换一次。
"""
简单选择排序：
- 对每个位置 i，从 i+1 到末尾找出最小值的索引 min_index
- 如果 min_index 与 i 不同，则交换两个元素
- 每轮只交换一次，降低了数据交换的次数
"""
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i # 假设当前 i 是最小的
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
data = [64, 25, 12, 22, 11]
selection_sort(data)
print("简单选择排序后：", data)
复杂度分析：
- 最坏/平均/最好情况时间复杂度：
O(n^2) - 空间复杂度：
O(1)，原地排序
冒泡排序
冒泡排序的核心思想就是通过相邻元素的比较与交换，将较大的元素逐步“冒泡”到序列的末尾。
"""
冒泡排序：
- 通过相邻元素两两比较，将较大的元素逐步“冒泡”到序列末尾
- 外层循环控制排序趟数，总共进行 n - 1 趟排序
- 内层循环逐个比较相邻元素，如果发现顺序错误，则交换位置
- 优化：如果某一趟排序中没有交换元素，则提前结束排序
"""
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False # 用于优化：如果本轮没有发生交换，说明已排序好
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 如果一轮比较中没有发生交换，说明数组已排序
break
data = [64, 25, 12, 22, 11]
bubble_sort(data)
print("冒泡排序后：", data)
动态过程：
复杂度分析：
- 最坏/平均情况时间复杂度：
O(n^2) - 最好情况时间复杂度（已经排序好）：
O(n) - 空间复杂度：
O(1)，原地排序
搅拌排序(双向冒泡)
搅拌排序的原理，通过反复从左到右和从右到左的遍历，逐步地将最小和最大的元素推到正确的位置。
请注意，如果在某一轮中没有发生任何交换，算法就会提前结束，因为数组已经有序。
"""
搅拌排序又称双向冒泡排序：
- 它是冒泡排序的变体，区别在于每轮排序包括两个方向：
- 从左到右，找到最大值冒泡到右端
- 从右到左，找到最小值冒泡到左端
- 每次循环后缩小边界区域（start 和 end），避免已排序区域的无效比较
- 若某一趟没有发生交换，说明序列已排好，可提前结束
优点：
- 相比普通冒泡排序，在某些场景下可以减少比较轮数
"""
def cocktail_shaker_sort(arr):
n = len(arr)
start = 0
end = n - 1
swapped = True
while swapped:
swapped = False
# 从左到右冒泡，将最大值移至最右侧
for i in range(start, end):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
if not swapped: # 若未交换，说明已排序好
break
end -= 1 # 缩小右边界
swapped = False
# 从右向左冒泡，将最小值移至最左侧
for i in range(end, start, -1):
if arr[i] < arr[i - 1]:
arr[i], arr[i - 1] = arr[i - 1], arr[i]
swapped = True
if not swapped: # 若未交换，说明已排序好
break
start += 1 # 缩小左边界
data = [64, 25, 12, 22, 11]
cocktail_shaker_sort(data)
print("搅拌排序后：", data)
注意：“双向冒泡排序”适合数据变化较少的场景，减少不必要的比较轮次。
复杂度分析：
- 时间复杂度：最坏/平均为
O(n^2)，最好为O(n)（已排好序时） - 空间复杂度：
O(1)，原地排序
归并排序
归并排序的核心思想（分治法）：
- 分解：将列表从中间拆分成左右两个子列表
- 递归排序：对两个子列表分别排序
- 合并：将两个有序子列表合并成一个有序列表
合并两个有序列表操作：
- 两个有序列表
left和right各自维护一个指针 - 比较
left[i]和right[j]，谁小就放到结果列表中，指针向后移动 - 如果一个列表先用完，则把另一个列表的剩余部分直接追加到结果中
def merge_sort(arr):
if len(arr) <= 1:
return arr # 递归终止条件：列表为空或只有一个元素，已排序
# 分解
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 左边排序
right = merge_sort(arr[mid:]) # 右边排序
# 合并两个有序子列表
return merge(left, right)
def merge(left, right):
merged = []
i = j = 0
# 比较并合并两个有序列表
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# 追加剩余元素（某个列表已经用完）
merged.extend(left[i:])
merged.extend(right[j:])
return merged
data = [64, 25, 12, 22, 11]
sorted_data = merge_sort(data)
print("归并排序后：", sorted_data)
动态过程：
复杂度分析：
- 归并排序是稳定排序，且其最坏、最优和平均时间复杂度都为
O(n log n)。
快速排序
快速排序使用分治法策略，把一个序列分成较小和较大的两个子序列，然后递归地排序两个子序列。
思路分析：
- 选取基准：常见做法包括选第一个、最后一个、中间一个或随机一个元素。
- 分区：遍历数组将小于等于
pivot的元素放到前面。 - 递归处理左右子数组：递归地对左半和右半进行快速排序。
- 递归终止条件：当子数组只有一个或零个元素时，不再继续递归，结束排序过程。
def quick_sort(arr):
"""快速排序入口函数，使用分治法"""
def _quick_sort(arr, start, end):
if start < end:
# 获取分区后 pivot 的最终位置
pivot_index = partition(arr, start, end)
# 递归排序左边部分
_quick_sort(arr, start, pivot_index - 1)
# 递归排序右边部分
_quick_sort(arr, pivot_index + 1, end)
def partition(arr, start, end):
"""对 arr[start:end+1] 进行分区，返回基准位置"""
pivot = arr[end] # 选取最后一个元素作为基准
i = start - 1 # 小于基准元素的最后位置
for j in range(start, end):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# 将基准元素放到正确位置
arr[i + 1], arr[end] = arr[end], arr[i + 1]
return i + 1
_quick_sort(arr, 0, len(arr) - 1)
return arr
if __name__ == "__main__":
data = [64, 25, 12, 22, 11]
sorted_data = quick_sort(data)
print("快速排序结果：", sorted_data)
复杂度分析：
- 快速排序平均时间复杂度是 O(n log n)，最坏是 O(n²)
注意：快速排序 不是稳定排序，若希望实现稳定排序（如归并排序），需使用不同策略。
查找算法
顺序查找
顺序查找（Sequential Search）是最基础的查找算法之一，也叫线性查找。
它从头到尾依次遍历列表中的每个元素，查找目标值。如果找到目标值，则返回其索引；否则，返回 -1 表示目标值不存在。
def sequential_search(arr, target):
"""
顺序查找（线性查找）
:param arr: 可迭代对象（列表、元组等）
:param target: 查找的目标值
:return: 如果找到，返回索引；否则返回 -1
"""
for index, value in enumerate(arr):
if value == target:
return index
return -1
data = [64, 25, 12, 22, 11]
target = 22
result = sequential_search(data, target)
if result != -1:
print(f"找到了目标值 {target}，索引为：{result}")
else:
print(f"未找到目标值 {target}")
复杂度分析：
- 时间复杂度：
O(n)，其中n是数组长度。最坏情况：目标元素不在列表中，或者目标元素位于最后一个位置。此时需要遍历整个列表n次。 - 空间复杂度：由于只使用了常数空间（
index和value），因此空间复杂度是O(1)。
总结：
适用于未排序的小型数据集列表，对于大规模数据不太适用。
折半查找
折半查找（Binary Search）是一种高效的静态查找算法，适用于已排序的数据序列（升序或降序）。其核心思想是通过不断将查找区间对半缩小，每次比较中间元素与目标值，从而决定下一步查找的区间。
该算法的时间复杂度为 O(log n)，在处理大规模数据时，相比线性查找（O(n)）具有显著的性能优势，是查找算法中的经典实现方式。
def binary_search(arr, target):
"""
折半查找
:param arr: 有序列表
:param target: 要查找的目标值
:return: 若找到返回索引，否则返回 -1
"""
start = 0
end = len(arr) - 1
while start <= end:
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
end = mid - 1
else:
start = mid + 1
return -1
data = [11, 12, 22, 25, 64]
target = 22
result = binary_search(data, target)
if result != -1:
print(f"找到了目标值 {target}，索引为：{result}")
else:
print(f"未找到目标值 {target}")
经典问题与算法
穷举法
穷举法又称为暴力破解法，通过列举所有可能的情况并逐一验证，直到找到符合条件的解。
特点：简单直接，适用于问题规模较小或解空间有限的场景，但效率低。
示例：解决“百钱买百鸡”问题
场景：
- 公鸡
5元一只，母鸡3元一只，小鸡1元三只 - 用
100元买100只鸡，问公鸡/母鸡/小鸡各多少只
这个问题的关键在于满足两个约束条件：
- 总钱数为 100 元：
5x + 3y + z/3 == 100 - 总鸡数为 100 只：
x + y + z == 100
可知：
x最大不能超过100 // 5 = 20y最大不能超过100 // 3 = 33z可以由100 - x - y推出，所以无需再循环- 提前判断
z % 3 == 0，再判断是否满足钱数条件
def main():
print("公鸡\t母鸡\t小鸡")
for x in range(21): # 公鸡最多20只
for y in range(34): # 母鸡最多33只
z = 100 - x - y
if z >= 0 and z % 3 == 0: # 小鸡数量必须是3的倍数
total_cost = 5 * x + 3 * y + z // 3
if total_cost == 100:
print(f"{x}\t{y}\t{z}")
if __name__ == "__main__":
main()
运行结果：
公鸡 母鸡 小鸡
0 25 75
4 18 78
8 11 81
12 4 84
示例2：解决“五人分鱼”问题
场景：
五个人 A、B、C、D、E 合伙捕鱼，晚上睡觉时鱼堆在一起。
第二天早上他们依次醒来，每次都：
- 把鱼分成 5 份；
- 扔掉 1 条多余的鱼；
- 拿走自己那份；
- 剩下的继续留给后面的人。
问：最少一共捕了多少条鱼才能满足每个人都可以这么操作？
思路：
这是一个经典的穷举 + 数学反推问题：
- 从最小可能的鱼数
fish = 1开始； - 对每一个尝试的
fish：- 模拟五次分鱼过程（五个人）；
- 每轮必须满足
(total - 1) % 5 == 0，即减 1 后能整除 5； - 如果 5 轮都满足条件，那这个数就是答案；
- 为了加速搜索，每次
fish += 5（因为必须减去 1 后能整除 5）；
def is_vaild(total):
for _ in range(5):
if (total - 1) % 5 != 0:
return False
total = (total - 1) // 5 * 4
return True
def find_min_fish():
fish = 1
while True:
if is_vaild(fish):
return fish
fish += 5 # 优化搜索步长
if __name__ == "__main__":
total_fish = find_min_fish()
print("最少鱼数为:", total_fish) # 最少鱼数为: 3121
贪心法
贪婪法：在对问题求解时，总是做出在当前看来是最好的选择，不追求最优解，快速找到满意解。
不回溯、不考虑后果，适用于满足“贪心选择性质”和“最优子结构”的问题。
示例：0-1 背包问题
场景：假设小偷有一个背包，最多能装 20 公斤赃物，他闯入一户人家，发现如下表所示的物品。
很显然，他不能把所有物品都装进背包，所以必须确定拿走哪些物品，留下哪些物品。
| 名称 | 价格（美元） | 重量（kg） |
|---|---|---|
| 电脑 | 200 | 20 |
| 收音机 | 20 | 4 |
| 钟 | 175 | 10 |
| 花瓶 | 50 | 2 |
| 书 | 10 | 1 |
| 油画 | 90 | 9 |
class Thing:
"""物品类，包含名称、价格、重量及单位价值（价格/重量）"""
def __init__(self, name, price, weight):
self.name = name
self.price = price
self.weight = weight
@property
def value(self):
return self.price / self.weight
def input_thing():
"""读取一行物品数据并返回元组 (name, price, weight)"""
name, price, weight = input().split()
return name, int(price), int(weight)
def main():
# 读取背包最大承重 & 物品数量
max_weight, num_of_things = map(
int, input("请输入背包容量和所有物品数量（用空格分隔）：").split())
all_things = []
print("请输入每件物品的信息（名称 价格 重量）")
for _ in range(num_of_things):
all_things.append(Thing(*input_thing()))
# 按单位价值排序（贪心策略：优先选单位价值高的）
all_things.sort(key=lambda x: x.value, reverse=True)
total_weight = 0
total_price = 0
selected = []
# 贪婪选择物品
for thing in all_things:
if total_weight + thing.weight <= max_weight:
selected.append(thing)
total_weight += thing.weight
total_price += thing.price
print("\n小偷拿走了这些物品：")
for item in selected:
print(f"- {item.name}（价格：{item.price}，重量：{item.weight}）")
print(f"\n总重量：{total_weight} kg")
print(f"总价值：{total_price} 美元")
if __name__ == "__main__":
main()
信息输入：
请输入背包容量和所有物品数量（用空格分隔）：20 6
请输入每件物品的信息（名称 价格 重量）
电脑 200 20
收音机 20 4
钟 175 10
花瓶 50 2
书 10 1
油画 90 9
输出结果：
小偷拿走了这些物品：
- 花瓶（价格：50，重量：2）
- 钟（价格：175，重量：10）
- 书（价格：10，重量：1）
- 收音机（价格：20，重量：4）
总重量：17 kg
总价值：255 美元
说明：
贪心算法实现的，它不能保证得到 0-1 背包问题的最优解。
- 在某些情况下，一个单位价值虽高但重量较大的物品可能会被贪心算法优先选中，导致背包空间迅速被占满，从而无法装入多个总价值更高的轻质物品，最终结果并非最优解。
- 若要得到最优解，应使用动态规划。
分治法
将复杂问题分解成若干个相同或类似的子问题，递归求解子问题后，再合并其解得到原问题的解。
分治法是递归思想的核心体现。
示例：归并排序（见上文）、快速排序、二分查找、Strassen矩阵乘法等。
回溯法
回溯法（Backtracking）是一种用于求解组合、排列、路径搜索等复杂问题的经典算法策略。其核心思想是：尝试不同路径进行搜索，若当前路径无法满足条件，则回退至上一状态并尝试其他可能。
回溯法的本质是尝试与撤销，通过深度优先搜索遍历解空间树，适用于需要穷举所有可能解的问题。它在诸如N皇后问题、全排列、子集生成、数独求解等问题中被广泛应用，是解决约束条件下组合问题的重要方法。
回溯法的核心步骤
- 选择：从当前状态出发，尝试一个可能的选项。
- 探索：递归地进入下一层，继续尝试下一个选择。
- 撤销：如果探索失败或已找到一个解，回退至上一状态并撤销选择。
- 终止条件：到达解空间的叶子节点或满足问题约束条件。
回溯法的典型应用场景
| 问题类型 | 示例 |
|---|---|
| 组合问题 | 从 n 个数中选出 k 个数的所有组合 |
| 排列问题 | 求一个数组的所有全排列 |
| 子集问题 | 求一个数组的所有子集 |
| 路径搜索 | 矩阵中的路径、迷宫问题 |
| 约束满足问题 | N 皇后问题、数独求解、图的着色问题 |
示例：骑士巡逻问题
场景：
骑士巡逻（Knight’s Tour）：在国际象棋棋盘上，骑士从某一格开始，按照规则移动（L形），尝试走遍棋盘的所有格子，且每格只走一次。
SIZE = 5 # 棋盘大小
total = 0 # 全局变量统计走法总数
show_solution = False # 是否打印每种走法
# 马可以走8个方向（行偏移，列偏移）
DIRECTIONS = [
(-2, -1), (-2, +1),
(+2, -1), (+2, +1),
(-1, -2), (-1, +2),
(+1, -2), (+1, +2)
]
def print_board(board):
"""打印棋盘"""
for row in board:
print(''.join(str(col).center(4) for col in row))
print()
def patrol(board, row, col, step=1):
"""递归回溯查找所有走法"""
global total
# 边界检测和当前位置是否已访问
if 0 <= row < SIZE and 0 <= col < SIZE and board[row][col] == 0:
board[row][col] = step # 标记当前格为第 step 步
if step == SIZE * SIZE:
total += 1
if show_solution:
print(f"第 {total} 种走法：")
print_board(board)
else:
# 尝试马走的8个方向
for dx, dy in DIRECTIONS:
patrol(board, row + dx, col + dy, step + 1)
board[row][col] = 0 # 回溯：撤销当前位置
def main():
board = [[0 for _ in range(SIZE)] for _ in range(SIZE)]
patrol(board, SIZE - 1, SIZE - 1) # 起点在右下角
print(f"\n共有 {total} 种走法")
if __name__ == "__main__":
main()
动态规划
动态规划（Dynamic Programming, DP）是一种用于解决具有最优子结构和重叠子问题特性的算法设计方法。其核心思想是通过将原问题分解为子问题，并记录子问题的解以避免重复计算，从而显著提升算法效率。
动态规划的两个关键性质是：
- 最优子结构（Optimal Substructure）：原问题的最优解可以通过子问题的最优解来构造。
- 重叠子问题（Overlapping Subproblems）：在递归求解过程中，子问题会被多次重复求解，动态规划通过记忆化或表格化的方式存储这些解，避免重复计算，节省计算时间。
实现方式通常包括：
- Top-Down（自顶向下）：递归 + 记忆化
- Bottom-Up（自底向上）：迭代 + DP 表格填充
动态规划广泛应用于：
- 背包问题（如 0/1 背包、完全背包）
- 字符串匹配问题（如最长公共子序列 LCS、编辑距离）
- 区间型问题（如矩阵链乘法、石子合并）
- 路径规划问题（如爬楼梯、不同路径）
- 图论问题（如 Floyd-Warshall 算法）
示例：解决最大子数组和的问题（Kadane 问题）
问题描述：
给定一个整数列表，可能包含正数、负数或 0，找出其中 连续子列表的最大和。连续子列表指的是索引连续的元素组成的子列表。
算法思路：
定义两个变量：
partial：以当前位置结尾的最大连续子数组的和overall：目前为止所有位置中遇到的最大子数组的和
状态转移公式：
partial = max(nums[i], partial + nums[i])，表示要么从当前位置重新开始，要么继续之前的子数组overall = max(overall, partial)
时间复杂度：O(N) -- 只需遍历一遍列表即可
def max_subarray_sum(nums):
"""
使用动态规划（Kadane算法）寻找最大连续子数组和。
:param nums: List[int], 整数列表
:return: int,最大连续子数组的和
"""
if not nums:
return 0 # 空列表返回 0
# 初始化两个变量
partial = overall = nums[0]
for i in range(1, len(nums)):
partial = max(nums[i], partial + nums[i])
overall = max(overall, partial)
return overall
if __name__ == "__main__":
# 输入格式：逗号分隔的整数
nums = list(map(int, input("请输入整数序列，以空格分隔：\n").split(",")))
result = max_subarray_sum(nums)
print("最大子数组和为：", result)
输出结果：
请输入整数序列，以空格分隔：
1, -2, 3, 4, -1, 2, 1, -5, 4
最大子数组和为： 9
本文由作者按照 CC BY 4.0 进行授权。