算法思维入门

🎯 核心问题

如何高效地解决问题？ 你可能遇到过这样的困惑：同一个问题，有人写的代码跑几秒就出结果，有人写的跑几分钟还在转。差别往往在于算法。本章带你理解算法的核心思维方式。

0. 全景图：算法是什么？

想象你要在一本字典里找一个单词：

方法一：从第一页开始，一页一页翻（线性查找）
方法二：根据首字母定位，再二分查找（二分查找）

两种方法都能找到，但效率天差地别。算法就是解决问题的方法。

算法思维：解决问题的方法不同策略解决不同类型的问题

二分查找每次排除一半，O(log n)

在有序数组中查找：

时间复杂度速查

O(1)常数最优，如数组访问

O(log n)对数很好，如二分查找

O(n)线性一般，如遍历

O(n log n)线性对数可接受，如快速排序

O(n²)平方较慢，如冒泡排序

O(2ⁿ)指数很慢，如暴力递归

核心思想：算法是解决问题的方法。好的算法能让程序效率提升几个数量级。理解算法思维，比记住具体算法更重要。

算法的核心指标：

指标	含义	为什么重要
时间复杂度	运行时间随数据量增长的趋势	预测大规模数据的性能
空间复杂度	内存占用随数据量增长的趋势	评估内存消耗
正确性	是否总能得到正确结果	算法的基本要求

📊 逐行解读这张表

时间复杂度：用大 O 表示法描述。O(n) 表示数据量翻倍，时间翻倍；O(n²) 表示数据量翻倍，时间变成 4 倍。

空间复杂度：同样用大 O 表示法。有些算法用空间换时间（如哈希表），有些用时间换空间（如压缩算法）。

正确性：算法必须对所有可能的输入都能给出正确结果。边界条件（空输入、极大输入）最容易出错。

1. 二分查找：每次排除一半

1.1 二分查找的原理

💡 二分查找如何工作？

前提：数据必须有序

过程：

找到中间元素
如果中间元素等于目标，找到！
如果目标小于中间元素，在左半部分继续
如果目标大于中间元素，在右半部分继续
每次排除一半，直到找到或确定不存在

时间复杂度：O(log n)

生活类比：猜数字游戏。我想一个 1-100 的数，你每次猜中间，我告诉你大了还是小了。最多猜 7 次就能猜中（因为 2⁷ = 128 > 100）。

1.2 为什么二分查找这么快？

数据量	线性查找	二分查找
100	100 次	7 次
1,000	1,000 次	10 次
1,000,000	1,000,000 次	20 次
1,000,000,000	1,000,000,000 次	30 次

💡 对数增长的威力

二分查找的时间复杂度是 O(log n)，这意味着：

10 亿数据，最多查找 30 次
1 万亿数据，最多查找 40 次

这就是对数增长的威力——数据量增加 1000 倍，查找次数只增加 10 次。

2. 排序：将无序变有序

2.1 常见排序算法

算法	时间复杂度	特点	适用场景
冒泡排序	O(n²)	简单但慢	教学、小数据量
选择排序	O(n²)	简单但慢	小数据量
插入排序	O(n²)	对近乎有序的数据快	小数据、近乎有序
快速排序	O(n log n)	实际最快	通用排序
归并排序	O(n log n)	稳定排序	需要稳定性的场景
堆排序	O(n log n)	原地排序	内存受限场景

2.2 为什么快速排序"快"？

💡 快速排序的原理

核心思想：分治法

选一个"基准"元素
把比基准小的放左边，比基准大的放右边
对左右两部分递归排序
合并结果

为什么快？

每次划分后，基准元素就到了最终位置
平均情况下，每次划分大约排除一半元素
时间复杂度 O(n log n)

生活类比：整理书架。先抽出一本书，把比它薄的放左边，比它厚的放右边。然后对左右两堆分别重复这个过程。

3. 递归：自己调用自己

3.1 递归的本质

💡 什么是递归？

递归是函数调用自身的编程技巧。

两个关键要素：

基本情况：什么时候停止递归？
递归步骤：如何把问题分解成更小的子问题？

经典例子：阶乘

function factorial(n) {
  if (n <= 1) return 1        // 基本情况
  return n * factorial(n - 1) // 递归步骤
}

生活类比：俄罗斯套娃。打开一个娃娃，里面是更小的娃娃，直到最小的那个打不开为止。

3.2 递归 vs 迭代

特性	递归	迭代（循环）
代码简洁度	通常更简洁	可能更复杂
内存消耗	较高（调用栈）	较低
性能	稍慢（函数调用开销）	更快
适用场景	树遍历、分治算法	简单重复任务

⚠️ 递归的陷阱

栈溢出：递归层次太深，调用栈空间耗尽。

解决方法：

改用迭代
使用尾递归优化（某些语言支持）
限制递归深度

4. 贪心算法：每步选最优

4.1 贪心的思想

💡 什么是贪心算法？

贪心算法在每一步都选择当前看起来最优的选择，希望最终得到全局最优解。

适用条件：

贪心选择性质：局部最优能导致全局最优
最优子结构：问题的最优解包含子问题的最优解

经典例子：硬币找零

目标：用最少的硬币凑出指定金额
贪心策略：每次选最大的硬币
结果：67 元 = 50 + 10 + 5 + 1 + 1（5 枚）

生活类比：登山时，每次都选最陡的路往上走。虽然不一定能到最高峰，但通常能到不错的位置。

4.2 贪心的局限性

⚠️ 贪心不一定得到最优解

反例：硬币找零

如果硬币面值是 [1, 3, 4]，要凑 6 元：

贪心：4 + 1 + 1 = 3 枚
最优：3 + 3 = 2 枚

贪心算法在这里失败了！

教训：贪心算法简单高效，但不总是能得到最优解。使用前要证明问题满足贪心条件。

5. 算法设计范式

范式	思想	典型算法	适用问题
分治	把问题分解成小问题	快速排序、归并排序	可分解的问题
贪心	每步选最优	最小生成树、霍夫曼编码	有贪心性质的问题
动态规划	记录子问题的解	背包问题、最短路径	有重叠子问题
回溯	试错，走不通就回退	八皇后、全排列	搜索问题

6. 总结：算法是解决问题的艺术

让我们用一个比喻总结各种算法思想：

思想	比喻	核心要点
二分查找	猜数字	每次排除一半
排序	整理书架	建立秩序
递归	俄罗斯套娃	化大为小
贪心	登山选路	局部最优

💡 核心启示

算法的本质是"效率"和"正确性"的平衡。

好的算法能让程序效率提升几个数量级
但过度优化可能引入复杂性
先保证正确，再追求效率

理解算法思维，比记住具体算法更重要：

分治：把大问题分解成小问题
贪心：每步选最优
动态规划：记录子问题的解
回溯：试错，走不通就回退

算法思维入门 ​

0. 全景图：算法是什么？ ​

1. 二分查找：每次排除一半 ​

1.1 二分查找的原理 ​

1.2 为什么二分查找这么快？ ​

2. 排序：将无序变有序 ​

2.1 常见排序算法 ​

2.2 为什么快速排序"快"？ ​

3. 递归：自己调用自己 ​

3.1 递归的本质 ​

3.2 递归 vs 迭代 ​

4. 贪心算法：每步选最优 ​

4.1 贪心的思想 ​

4.2 贪心的局限性 ​

5. 算法设计范式 ​

6. 总结：算法是解决问题的艺术 ​

延伸阅读 ​