学习笔记

常用的算法

#数据结构与算法 #编程学习

常用算法 81/365

六、算法

1.我们如何判断算法的好坏

同一个问题，我们可能有很多种解法。就像去罗马，有的人坐飞机，有的人开车，有的人走路。那怎么判断哪条路更快呢？

计算机科学家提出了 大 O 复杂度 的概念，它用来衡量当数据量增加时，算法运行时间的增长速度。

你可以把它理解成一个公式：

  • O(n)：数据多一倍，时间多一倍（线性增长）。

  • O(n²)：数据多一倍，时间会增加成平方（增长得更快）。

下图展示了不同复杂度在数据量增加时的变化趋势：

（横轴：数据数量；纵轴：运行时间）

![[截屏2025-08-04 19.42.49.png]]

除了时间复杂度，还有 空间复杂度（内存占用情况），不过空间复杂度的计算相对复杂，所以在日常中，我们更多用 大 O 来评估算法。

在下面我会直接给出算法的复杂度，不做证明。

2. 递归算法—百丈高楼平地起

递归的意思是：自己调用自己来解决问题。

它分成两个过程：

  1. 向里走 —— 不断把问题拆成更小的同类问题。

  2. 向外回 —— 把小问题的答案组合成大问题的答案。

举个生活例子：

如果我想学会编程 → 我得先学会前端和后端。

要学会前端和后端 → 我得先学会计算机基础。

等我学完计算机基础，再去学前端和后端，就会更容易。

这就像一个套娃，必须先把最小的娃拿出来，才能一层层往外完成。

递归和 栈（Stack） 关系很紧密——每进入一层递归，就像往栈里压一个任务；当任务完成，就从栈里弹出来。

2.1 递归算法的三个要素

  1. 结束条件（不再调用自己）

    就像爬楼梯的问题，爬到最后一层就结束。

  2. 问题可缩小

    大问题能转化成一个小一点的同类问题，比如：

    爬 100 层楼梯 = 爬 99 层楼梯 + 1 层楼梯

  3. 调用自身

    在上面楼梯的例子里，爬99层楼梯 这个步骤就会再次调用同样的逻辑。

2.2 经典例子：汉诺塔问题，复杂度O(2^n)

![[截屏2025-08-04 20.25.20.png]]

故事背景

在一个寺庙里，有三根柱子：A、B、C。

A 柱上有 64 个大小不同的黄金盘，按从大到小排列。任务是：把这些盘全部搬到 C 柱上。规则是：

  1. 一次只能搬一个盘。

  2. 大盘不能放在小盘上面。

递归思路

  • 第一步（大问题拆解为小问题）：要想把最底下那个最大的盘子（第n个）从A移动到C，我必须先把它上面的 n-1 个小盘子，全部从A移走，放到不碍事的B柱上。这个任务就是 Hanoi(n-1, A, C, B)。（注意柱子的角色变化！）

  • 第二步（解决当前最小问题）：现在A柱只剩最大的盘子了，我直接把它从A移动到C。

  • 第三步（解决剩下的那个小问题）：最后，我再把B柱上的那 n-1 个盘子，从B借助A，移动到C柱上。这个任务就是 Hanoi(n-1, B, A, C)。

  • tips ：大家这里可能不太好理解，这里把n个盘子分成两个盘子——一个盘子是第n个盘子，一个盘子是上面的n-1个盘子当成一个整体。

总结：

你看，我们把“移动n个盘子”这个大问题，完美地拆解成了两个“移动n-1个盘子”的小问题，和一个“移动1个盘子”的简单问题。这就是递归的魔力。

# Hanoi(盘子数量, 源柱, 辅助柱, 目标柱) 
def hanoi(n, source, auxiliary, target): 

	# 1. 终止条件：如果只有一个盘子 
	if n == 1: 
		print(f"把盘子 1 从 {source} 移动到 {target}")
		return
		
	# 2. 递归调用第一步：把n-1个盘子，从源柱，借助目标柱，移到辅助柱 
	hanoi(n - 1, source, target, auxiliary) 
	
	# 3. 解决当前最小问题：把最大的那个盘子，从源柱移到目标柱 
	print(f"把盘子 {n} 从 {source} 移动到 {target}") 
	
	# 4. 递归调用第二步：把n-1个盘子，从辅助柱，借助源柱，移到目标柱 
	hanoi(n - 1, auxiliary, source, target) 

#让我们来试试移动3个盘子 
hanoi(3, 'A', 'B', 'C')

3. 排序算法

排序算法就是把一堆数据按一定规则排好顺序，比如从小到大、从大到小。

生活中随处可见，比如打扑克牌时按牌面排序，查字典的时候，电子邮件的日期先后的时候

下面用简单的例子来看看几种常见的排序方法。

3.1 冒泡排序 — O(n²)

想象你在水里吹泡泡，最大的泡泡会慢慢浮到水面。

冒泡排序的原理就是这样：

  • 每次比较相邻两个数，如果顺序错了，就交换位置

  • 一轮下来，最大（或最小）的数就被“冒”到最后

  • 重复这个过程，直到所有数据排好

示例：

[5, 3, 8, 2]  
第一轮：3和5换 → [3, 5, 8, 2]  
8和2换 → [3, 5, 2, 8]  
第二轮继续……

3.2 选择排序 — O(n²)

如果你要在一堆牌里找最小的牌，你会先找出最小的，放到一边，然后再在剩下的牌里找最小的……

这就是选择排序的思路：

  • 每一轮找出最小（或最大）的数

  • 把它放到正确的位置

  • 剩下的重复同样的操作

3.3 快速排序 — O(n log n)

快速排序可以理解成**“分而治之”**：

  1. 先从数组里随便选一个数作为“基准值”（pivot）

  2. 把比它小的放左边，比它大的放右边

  3. 再对左右两边分别重复这个过程

  4. 最终左右合并，就是有序的了

它的速度通常比冒泡和选择快很多，因此用得很广。

3.4 为什么快速排序比冒泡/选择排序快？

简单来说，快速排序快，是因为它不是一步步“傻排”，而是先把数据“劈开”，再分别处理。

  • 冒泡和选择排序每次只确定一个位置，得一遍一遍循环，效率低

  • 快速排序会先挑一个“基准值”，把数据分成两堆，然后分别处理，这样每一轮都能大幅减少工作量

不过，快速排序需要额外的内存空间来保存中间的分组结果（在程序里通常用栈来存），所以它是用更多空间来换更快的速度。

4. 贪心算法——兔子要吃窝边草

贪心算法的核心思想很简单：

每一步都选当前看起来最好的方案，不管未来。

就像一只兔子，只吃离自己最近的草，不会去考虑远处是否有更好的草。

例子

我手里只有很少的钱，但想炒股。

  • 面前有几只股票，价格和收益率各不相同

  • 如果先买价格高的股票，可能剩下的钱买不了其他股票，就闲置了

  • 贪心算法会让你先买收益率最高的股票，剩下的钱再买次高的，直到买不动为止

这种做法能保证每一步是局部最优，但不一定能得到全局最优（可能错过组合起来更好的方案）。

4.1 贪心算法的使用指南

场景适合不适合
问题特性每一步的最优解能直接导向全局最优（如合理面额的找零问题）当前最优会阻碍后续更优（如背包问题中的“组合最优”）
数据规模数据量大但规则简单（如任务调度、活动安排）数据依赖复杂，需要多步推演（如复杂投资组合）
计算要求追求快速、简单的计算追求绝对最优解，不怕复杂计算

4.2 贪心翻车案例

走迷宫的“右手法则”

你在一个复杂的迷宫里，每次都优先选择离出口方向最近的路，看起来好像越来越接近出口，但实际上可能会走到一个死胡同里，甚至绕很远的弯。

  • 每一步都是局部最优（离出口更近）

  • 但因为不考虑全局结构，结果可能是卡死或走了更长的路

教训

贪心算法快，但它的眼睛只有“一步远”。如果全局路径不是单调最优，它就可能“掉坑里”。

贪心算法更多的是一种不得不的选择，找不到更好的算法，所以只能使用这种局部最优的算法。

5. 动态规划

动态规划（Dynamic Programming，简称 DP）听起来高深，其实它的核心思想是：

把问题拆小，把小问题的答案记下来，避免重复计算。

就像一个游戏角色在迷宫中走路，如果你记住了走到每个格子最快的方式，下次就不用重新尝试，直接用现成答案——这就是动态规划的精髓。

5.1 为什么叫“动态规划”？

  • 动态：问题是一步步推进的，每一步的最优解依赖于前面几步的结果。

  • 规划：你在每一步都要规划一个最优策略，不走回头路。

简单说：“规划未来，记住过去。”

5.2 使用指南

  1. 能不能把问题拆成子问题？（有无最优子结构）

  2. 子问题是否重复出现？（有无重叠子问题）

  3. 能否定义一个数组来存子问题答案？（设计状态表示）

  4. 能否用状态转移方程从前一步推出当前？（设计状态转移方程）

举例：

  • 斐波那契数：

    fib(n) = fib(n-1) + fib(n-2)

    你会反复算 fib(3)、fib(4)……

  • 背包问题：

    不同选择路径会遇到相同的“剩余容量 + 剩余物品”组合。

  • 排程问题（如果资源有限 + 任务有依赖）：

    多个排法会遇到相同的“任务集 + 时间窗口 + 资源状态”

5.3 动态规划 VS 递归 VS 贪心

算法特点适用场景
递归思维清晰，代码简洁，但效率低（容易重复计算）问题规模小，或需要“自顶向下”拆解
贪心速度快，但可能不是最优解局部最优等于全局最优的情况
动态规划记忆所有历史，找到真正最优解，适合多步决策问题需要“最优子结构 + 重叠子问题”的场景

5.4 动态规划的应用场景

场景例子复杂度（一般）
最短路径地图导航、棋盘游戏O(n²) 或 O(mn)
最值问题最大利润、最多金币、最长上升子序列O(n)、O(n²)
计数问题硬币找零、组合数O(n×k)
背包问题容量限制下的最大价值O(n×w)

6. BFS(广度优先搜索)——用你的人生画圆

6.1 场景：寻找你失散多年的小学同学

想象一下，你要在一个庞大的人际网络中，寻找一位失散多年的小学同学。你怎么找最高效？

你可能会这么做：

  1. 第一步：你先问遍你所有的“直接好友”（第一层关系），把他们都记录在一个小本本上，排好队。

  2. 第二步：然后，你按照小本本上的顺序，逐一去问你的第一个好友：“你所有的好友里，有认识我要找的人吗？” 问完之后，把他所有的好友（你的第二层关系），也排着队，续写到你的小本本末尾。

  3. 第三步：你继续问你的第二个、第三个好友… 直到把你的所有“一层好友”都问完。

  4. 第四步：接着，你再从小本本上，找到你好友的好友（第二层关系），开始重复这个过程…

你看，你的搜索路径，就像一块投入湖面的石头，激起的涟漪一样：一层一层地、均匀地向外扩散。 你先探索完所有离你“1层关系”的人，再探索所有“2层关系”的人，以此类推。

这就是广度优先搜索（BFS）。它像一个耐心的、地毯式搜索的侦探，确保在你到达“第n层”关系之前，已经彻底检查完了所有“第n-1层”的关系。

技术实现：
为了实现这种“一层层”的搜索顺序，BFS依赖于一种叫**“队列”（Queue）的数据结构。它就像我们在食堂排队打饭，讲究“先进先出”**。你先把你的直接好友放进队列，然后取出一个，再把他所有的好友放到队尾，周而复始。

复杂度：它的时间复杂度是O(V+E)，其中V是顶-点（人数），E是边（关系）。简单来说，它需要把每个人、每条关系都检查一遍。

**6.2 人生的启示：最短的路径

BFS保证能帮你找到**“最短路径”。就像那个著名的“六度分隔理论”**所揭示的，通过BFS，你总能以最少的中间人，找到世界上任何一个人。

这在人生中意味着什么？
它意味着，如果你想最快地达成一个功利性的目标——比如找到一个能帮你办事的“关键先生”——BFS是最优策略。

但它的代价是**“耗时巨大”。因为它需要你探索整个地图中，所有与目标同等距离内的可能性。** 你的人生，会因此变得像一张均匀铺开的大饼，广阔，但可能缺乏深度和惊喜。

但另一方面，你的人生总会遇到属于你的天地，只要你敢于像BFS一样，去探索每一种可能性。但这很耗费时间，也需要巨大的耐心。

7. 狄克斯特拉算法 (Dijkstra’s Algorithm) —— 人生的最优权衡

7.1 场景：规划你的十一长假自驾游

现在，问题变得复杂了。你不再是简单地寻找“最短的路径”，而是要寻找一条**“成本最低”**的路径。

从北京到上海，你可以选择：

  • 路线A：路程最短，但要翻山越岭，油费和时间成本很高。

  • 路线B：路程稍长，但全程高速，路况好，总花费最低。

  • 路线C：风景最美，但耗时最长，成本也最高。

每一段路，都有一个**“权重”**（Weight），这个权重可以是距离、时间、油费、过路费，甚至是“疲劳指数”。你的目标，是找到一条从起点到终点，总权重最小的路线。

狄克斯特拉算法，就是解决这个问题的“导航之神”。

它的核心思想，是一种聪明的**“贪心策略”**：

  1. 第一步：从起点出发，看看所有能直接到达的城市，选择那个**“成本最低”**的城市（比如天津），先开过去。

  2. 第二步：到达天津后，你更新一下你的“地图”认知。你可能会发现，从天津再去济南，比你原计划从北京直接去济南，总成本要更低。于是，你在地图上，把“北京到济南”的路线，默默地换成了“北京-天津-济南”这条更优路线。

  3. 第三步：接下来，你再从所有“已知的、但还没去过”的城市里（比如北京能直达的石家庄，和刚更新过的济南），再选择一个当前总成本最低的，开过去。

  4. 重复这个过程：每一次都选择“当前看起来最优”的一步，并不断地用新发现的路径，去“优化”你对整个地图的认知，直到你到达终点上海。

复杂度：通过一些优化，它的时间复杂度可以做到O(E log V)。

7.2 人生的启示：每一步都选最优，就是全局最优吗？

狄克斯特拉算法告诉我们一个深刻的道理：在每一个人生的十字路口，都做出那个当下看起来“成本最低”或“收益最高”的选择，并不断地根据新情况调整未来的规划，最终，你就能走出一条通往目标的、全局最优的道路。

这是一种典型的“精明的现实主义者”的人生哲学。它高效、务实，能让你在资源有限的情况下，实现利益最大化，但前提是可以重来，我可以不断地重复，例如我探索出来了从北京到上海的最优通勤方式，但很多时候我们是不可以重来的，如果你今天收了几十万的好处费，当你发现这个方式不是最优的时候，你是不可能有机会重新选择的。

算法可以重来，人生不可以重来，算法拥有全局的视野信息，人生没有。

8. DFS(深度优先搜索)——不撞南墙不回头

8.1 场景：探索一个巨大的地下迷宫

现在，你是一个手持火把的探险家，进入了一个岔路繁多的黑暗迷宫。你的目标，是找到出口。

你会怎么做？你大概率会：

  1. 第一步：遇到第一个岔路口，随便选一条（比如左边），然后一头扎进去。

  2. 第二步：继续往前走，遇到新的岔路口，再随便选一条，继续深入。

  3. 第三步：你就这样**“一条路走到黑”**，直到你撞上南墙（死路），或者发现这个路的尽头又回到了你之前走过的地方。

  4. 第四步：这时，你才会**“回溯”**（Backtracking），退回到上一个岔路口，选择你当时没选的那条路（比如右边），继续深入探索。

这就是深度优先搜索（DFS）。它像一个执着的、甚至有点“一根筋”的冒险家，它的策略是：先抓住一条线索，就死追到底，不撞南墙不回头。

技术实现：
为了实现这种“深入-回溯”的路径，DFS天生就适合用我们之前讲过的**“递归”**来实现，因为它完美地利用了“栈”结构来保存我们路过的岔路口信息。

复杂度：和BFS一样，也是O(V+E)。

8.2 人生的启示：专注与迷失的悖论

DFS的人生哲学，是**“专注”与“极致”**。
它代表了那种一旦认准一个方向，就倾尽所有资源，深度钻研，不达目的誓不罢休的“专家精神”或“理想主义者”。

  • 优点：这种策略，更有可能让你在某个单一领域，达到前人未及的深度，从而发现隐藏在地图深处的、不为人知的“宝藏”。你的人生，会因此充满深度和故事性。

  • 缺点：它的风险极高。你可能会在一个错误的方向上，浪费掉大量的时间和生命。你可能会在撞了无数次南墙，心力交瘁地回到起点时，才发现，那个正确的出口，就在当初你没选择的另一条路上。

BFS画出了一个广阔的圆，而DFS，则画出了一条曲折的、深邃的线。

七、小结

你也许会忘了算法的名字，忘了什么是栈，什么是图。

但我更希望你记住一件事——当你在人生中遇到迷茫、困顿、或难以抉择的问题时，不妨试着把它当作一个“算法问题”来思考。

拆解目标，识别约束，寻找路径，评估代价。

你可以问问 AI，也可以回头翻翻这份笔记，也许某个算法的思路，正好能给你带来一丝启发。

这是一堂算法课，但更像是一把钥匙。

它不为你提供答案，而是教你：如何找到通往答案的路径。