欢迎来到算法分类！

你好！在本章中，我们将探讨计算机科学家是如何对不同的算法进行「评分」与分组的。你可以把算法想象成食谱：有些食谱制作迅速但过程混乱，而有些则费时但能做出完美的成品。看完这份笔记后，你将能够判断两种解决问题的方法，并根据效率决定哪一个才是「赢家」。

如果起初觉得有点复杂，别担心！ 我们基本上只是在学习如何比较工具，找出最适合特定工作的那个。

1. 什么是「好」的算法？

在分类之前，我们需要知道我们在寻找什么。根据课程大纲，我们从以下三个主要方面来评估一个计算机系统（及其算法）：

  • 正确性 (Correctness)： 它是否真的解决了问题并给出正确答案？
  • 效率 (Efficiency)： 它的执行速度有多快（时间效率），以及它占用多少内存（空间效率）？
  • 可维护性 (Maintainability)： 代码是否容易让其他人阅读并在日后进行修正？

效率的取舍 (The Efficiency Trade-off)

在计算机科学中，我们经常需要在速度与内存之间做出选择。这就像搬家一样：你可以开一辆小型车来回跑 20 趟（内存使用量低，但耗时长），或者雇佣一辆大型卡车一次搞定（占用很多「空间」，但速度极快）。

快速复习：评估准则

记住 CEM：
C - Correctness (正确性：它能运作吗？)
E - Efficiency (效率：它够快/够精简吗？)
M - Maintainability (可维护性：我读得懂吗？)

2. 搜索算法分类

搜索是指在列表中寻找特定项目。我们主要关注两种类型：线性搜索 (Linear Search) 和 二分搜索 (Binary Search)。

线性搜索 (Linear Search)

这是最「简单」的搜索方式。你从列表的第一个项目开始，逐一检查每一个项目，直到找到你要找的目标，或者查完整个列表。

  • 效率： 通常较低。如果你的目标在一百万个项目的列表末端，你就必须执行一百万次搜索！
  • 条件： 适用于任何列表（无论是否有序）。

二分搜索 (Binary Search)

这是一种更聪明的「分治法」(Divide and Conquer) 算法。它会先跳到列表的中间，判断目标是在上半部还是下半部，然后舍弃不需要的那一半。重复这个步骤，直到找到目标为止。

  • 效率： 非常高。随着列表长度增加，它的寻找速度远快于线性搜索。
  • 条件： 列表必须先经过排序 (ordered)。

类比：想象你在字典里找一个词。线性搜索就像是从 'A' 开始阅读每一个字。而二分搜索则是把书翻到中间，看看你的目标词是在那一页之前还是之后，然后根据判断继续翻阅。

常见的错误陷阱

切记： 你不能在杂乱、未排序的列表中使用 二分搜索。如果列表没有排序，你就只能使用 线性搜索。

重点总结： 对于小型或未排序的列表，请使用 线性搜索。对于大型、已排序的列表，请使用 二分搜索 以获得更好的时间效率。

3. 排序算法分类

排序是指将混乱的列表按顺序排列（例如按字母顺序或由小到大）。我们来看 冒泡排序 (Bubble Sort) 和 归并排序 (Merge Sort)。

冒泡排序 (Bubble Sort)

这个算法会以「回合」方式扫描列表。它会比较相邻的两个项目，如果顺序错误就交换它们。最大的项目会像气泡一样「浮」到列表的末端。

  • 时间效率： 对于大型列表来说，通常效率极低且缓慢。
  • 内存效率： 非常优异，因为它是「原地」(in-place) 排序，不需要额外的存储空间。
  • 你知道吗？ 高效版本的 冒泡排序 如果在整轮扫描中没有进行任何交换，可以提早结束——这代表列表已经排序完成了！

归并排序 (Merge Sort)

这是一个较复杂的算法。它会将列表拆分成极小的片段（单个项目），然后再按正确顺序将它们合并起来。

  • 时间效率： 处理大量数据时，速度比冒泡排序快得多。
  • 内存效率： 较冒泡排序低，因为它在处理过程中需要额外的内存来存放那些被「拆开」的片段。

逐步比较

要决定使用哪种排序法，请参考以下因素：

  1. 有多少数据？ 如果是巨量列表，归并排序在速度上完胜。
  2. 你有多少内存？ 如果内存空间非常有限（例如在微型芯片上），冒泡排序可能较为合适。
  3. 列表是否已经部分排序？ 如果列表几乎已经排好，冒泡排序会相当快；而归并排序则无论资料状态如何，所需时间大致相同。
记忆小撇步：排序总结

「Bubble 是 Basic（基本且慢），Merge 是 Mighty（强大且快）！」

重点总结： 冒泡排序容易撰写但速度慢。归并排序适合处理大数据但会占用较多内存。

4. 复习总结表

使用下表快速比较我们所介绍的算法：

算法 类型 主要优点 主要缺点
线性搜索 搜索 适用于未排序的数据。 在大型列表中速度缓慢。
二分搜索 搜索 速度极快。 数据必须先排序。
冒泡排序 排序 占用极少内存。 在大型列表中非常缓慢。
归并排序 排序 处理大型列表速度极快。 使用较多内存。

最终小贴士： 当考试要求你比较算法时，请务必提到时间效率（速度）以及数据的初始状态（是否已排序？是否为大型列表？）。