算法思维入门

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

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

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

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

前提：数据必须有序

过程：

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

时间复杂度：O(log n)

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

第一列（数据量）：要查找的数据有多少。可以看到数据量从 100 增长到 10 亿（扩大了 1000 万倍！）

第二列（线性查找）：最"笨"的方法，从第一个开始一个一个找。查找次数等于数据量，数据量越大，查找次数越多。

第三列（二分查找）：聪明的方法，每次排除一半。查找次数只和数据量的对数有关，即使 10 亿数据也只需要 30 次！

对比结论：当数据量达到 100 万时，线性查找需要 100 万次，二分查找只需要 20 次——差距达 5 万倍！

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

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

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

冒泡排序：最基础的排序算法，就像水底的气泡往上冒一样。简单易懂，但速度最慢。适合学习排序思想，不适合实际使用。

选择排序：每次选出最小的放到前面。也很简单，但无论数据是否有序都要做同样多的比较。

插入排序：像打扑克牌时整理手牌一样。把每个元素插入到前面已经排好序的部分中。对近乎有序的数据效率很高。

快速排序：实际开发中最常用的排序。平均情况下最快，但最坏情况（数据已经有序）会退化到 O(n²)。

归并排序：采用"分而治之"的思想，总是 O(n log n)，但需要额外空间。适合需要稳定排序的场景。

堆排序：利用堆这种数据结构的排序，原地排序（不需要额外空间），但实际运行往往比快速排序慢。

核心思想：分治法

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

为什么快？

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

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

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

两个关键要素：

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

经典例子：阶乘

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

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

代码简洁度：递归通常只需要几行代码就能表达复杂的逻辑（如遍历树结构），而用循环可能需要更多的变量和嵌套。

内存消耗：递归会使用"调用栈"来保存每一层的信息，就像叠盘子一样，每递归一层就多一个盘子。循环则不需要这种开销。

性能：每次函数调用都有开销（参数传递、栈操作等），所以递归通常比循环慢一些。

适用场景：递归擅长处理本身就是递归结构的问题（如文件树、DOM 树）；循环擅长简单的重复操作（如遍历数组）。

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

适用条件：

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

经典例子：硬币找零

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

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

分治：把大问题拆成小问题，分别解决后再合并。就像整理房间，先分成客厅、卧室、厨房分别打扫，最后整体整洁。

贪心：每步都选当前最好的，不考虑长远后果。像吃饭时先挑最喜欢吃的菜，可能不是最优的吃法，但速度快。

动态规划：记住中间结果，避免重复计算。像记笔记，下次遇到同样问题直接查答案，不用重新推导。

回溯：走不通就退回来重试。像走迷宫，此路不通就返回上一个路口尝试别的路。

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

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

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

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