A Level 计算机科学 (9618) 学习笔记

第 19 章：计算思维与问题解决 (A Level 内容)

欢迎来到 A Level 计算机科学中最令人兴奋且实用的章节之一！
计算思维的核心在于如何分析复杂问题，并设计出计算机能够执行的有效解决方案。这不仅仅是编写代码，更是像计算机科学家一样思考。

在本章中，我们将加深对高级算法（如搜索和排序）的理解，探索被称为抽象数据类型 (ADTs) 的强大数据结构，并掌握递归这一精妙的技术。这些技能是构建高效且可扩展的软件解决方案的基础。

19.1 算法与效率

19.1.1 高级搜索方法

我们已经了解了如何搜索数据，现在来比较两种核心方法：

线性搜索 (Linear Search)

这是最简单的搜索方法。

  • 工作原理： 从第一个元素开始，按顺序检查列表中的每一项，直到找到目标项或到达列表末尾。
  • 适用场景： 非常适合小型列表或未排序的列表。
  • 类比：想象在装满杂乱纸张的鞋盒里找一张特定的收据，你必须一张一张地翻找。
二分搜索 (Binary Search)

二分搜索效率极高，但它有一个至关重要的前提条件。

使用条件： 数据结构（例如数组或列表）必须是已排序的。

步骤流程：

  1. 找到列表的中间项。
  2. 将中间项与目标值进行比较。
  3. 如果匹配，则搜索结束。
  4. 如果目标值较小，则忽略列表的右半部分（以及中间项）。
  5. 如果目标值较大，则忽略列表的左半部分（以及中间项）。
  6. 在剩余的一半中重复上述过程，直到找到目标项或子集为空。

类比：“猜数字”游戏（20个问题）。每一次比较都会将搜索空间减半。

性能表现： 由于每一步都将列表减半，随着数据项数量 (N) 的增加，二分搜索的性能远优于线性搜索。

快速回顾：搜索

线性搜索： 简单，适用于未排序数据。在大规模 N 时较慢。

二分搜索： 必须已排序。在大规模 N 时非常快。

19.1.2 排序算法

排序是将数据按特定顺序排列的过程。你必须能够编写并追踪两种基本排序算法的伪代码：

冒泡排序 (Bubble Sort)

这通常是最容易理解的算法，但也是效率最低的算法之一。

  • 工作原理： 重复遍历列表，比较相邻元素，如果顺序错误则交换它们。
  • 效率： 在最坏的情况下（如果列表是逆序排列的），冒泡排序需要很长时间，因为需要进行大量的交换。
  • 助记：想象较轻的（较小的）泡泡浮到顶部（或者较重的项沉到底部），经过多轮扫描后完成排序。
插入排序 (Insertion Sort)

插入排序通常比冒泡排序更高效，特别是在处理小型或部分已排序的列表时。

  • 工作原理： 它一次构建一个已排序的序列。它遍历输入元素，并将每个元素插入到已排序部分中的正确位置。
  • 类比：整理手中的扑克牌。你保持手中的牌已排序，每拿到一张新牌，就找到它的正确位置并插入。

你知道吗？ 数据的初始顺序对排序算法所需的时间有重大影响。如果数据已经是大部分有序的，插入排序会比冒泡排序快得多。

19.1.3 抽象数据类型 (ADTs)

抽象数据类型 (ADT) 是数据结构的数学模型。关键在于，它定义了数据存储机制以及可以对这些数据执行的操作集。

使用 ADT 的主要好处是抽象化：我们只关心数据结构“做什么”（即操作），而不关心它是“如何实现的”（例如，使用数组还是链表）。

栈 (Stack)
  • 原则： LIFO（后进先出）。最后添加的项是第一个被移除的项。
  • 关键操作：
    • PUSH (入栈)： 将项添加到栈顶。
    • POP (出栈)： 移除并返回栈顶的项。
  • 实现： 通常使用数组实现，配合一个指针（或索引）来记录“栈顶”位置。
  • 应用场景：用于递归（调用栈）、软件中的撤销机制以及表达式求值。
队列 (Queue)
  • 原则： FIFO（先进先出）。第一个添加的项是第一个被移除的项。
  • 关键操作：
    • ENQUEUE (入队)： 将项添加到队列末尾。
    • DEQUEUE (出队)： 移除并返回队列前端的项。
  • 实现： 通常使用数组实现，需要维护“队首”和“队尾”两个指针。
  • 应用场景：用于操作系统（任务调度）、打印队列以及仿真系统。
链表 (Linked List)
  • 概念： 一种由节点组成的动态结构。每个节点包含数据项和一个指向序列中下一个节点的指针（或引用）。
  • 优点： 插入和删除操作非常高效，因为只需更新指针，无需像数组那样移动整个数据集。
  • 实现： 可以使用两个平行数组实现（一个用于存储数据，一个用于存储指针/索引）。
  • 关键操作： 需要编写算法通过指针遍历链表，从而实现对项的查找、插入和删除。
二叉树 (Binary Tree, BT)
  • 概念： 一种层级结构，每个节点最多有两个子节点（左子节点和右子节点）。
  • 组织方式： 节点左子树中的数据总是小于节点数据；右子树中的数据总是大于节点数据。这被称为二叉搜索树 (BST)。
  • 关键操作： 需要编写算法来查找、插入和删除项，利用层级结构来加速搜索（性能与二分搜索类似）。
图 (Graph)

图是一种用于建模对象间关系的 ADT。

  • 关键特征：
    图由顶点（节点）和边（连接或链路）组成。
    边可以是有向的（单向）或无向的（双向），并且可能带有权重（成本）。
  • 应用场景： 图非常适合用于地图导航、网络拓扑、路由算法（如 GPS 中使用的算法）以及社交媒体关系建模。

注：尽管图在人工智能（AI，特别是第 18.1 节）中很重要，但你只需要理解图 ADT 的关键特征并解释其使用理由，不需要编写其结构或遍历的代码，除非是 18.1 节中学习的算法（如 A* 和 Dijkstra）。

19.1.4 使用大 O 表示法比较算法

执行相同任务（如搜索或排序）的不同算法，可以根据其时间复杂度（速度）和空间复杂度（内存占用）进行比较。这通常通过大 O 表示法 (Big O Notation) 来量化。

什么是大 O？

大 O 表示法描述了当参数趋向于特定值或无穷大时，函数的极限行为。在计算机科学中，它告诉我们当输入规模 (\(N\)) 变得非常大时，算法的性能（时间/内存）是如何缩放的。

常见的复杂度：
  • \(O(1)\) - 常数时间： 无论输入规模如何，操作所需时间都相同。
    例如：通过索引访问数组中的元素。
  • \(O(\log N)\) - 对数时间： 时间随规模增长非常缓慢；每一步工作量都会减少。
    例如：二分搜索。如果你将输入规模增加一倍，仅需增加一步操作。
  • \(O(N)\) - 线性时间： 所需时间与输入规模成正比。
    例如：线性搜索。如果你将输入规模增加一倍，所需时间也会增加一倍。
  • \(O(N^2)\) - 平方时间： 所需时间呈指数级增加（N 乘以 N）。这通常发生在算法对数据使用了嵌套循环时。
    例如：冒泡排序和插入排序（在最坏情况下）。

核心要点： 当 N 很大时，\(O(\log N)\) 远好于 \(O(N)\)，而 \(O(N)\) 又远好于 \(O(N^2)\)。掌握大 O 表示法有助于我们论证使用特定算法的合理性（例如，在处理大型已排序数据库时选择二分搜索而非线性搜索）。

19.1 学习小结

必须根据数据结构（是否已排序？）和预期的输入规模 (N) 来选择高效的算法。大 O 表示法是衡量这种效率的标准工具。

19.2 递归 (Recursion)

递归是一种强大的技术，通过将问题分解为相同问题的较小实例，直至达到一个简单的、易于解决的基本情况，来解决问题。

递归的基本特征

每一个成功的递归程序都必须包含两个基本要素：

  1. 基本情况 (Base Case / 终止条件)： 这是停止递归的条件。当达到基本情况时，函数返回一个值而不再进行递归调用。如果没有基本情况，函数将无限运行，导致栈溢出错误。
  2. 递归步骤 (Recursive Step)： 这是函数调用自身的地方，通常参数会更接近基本情况，问题的规模会逐步减小。

示例：计算阶乘 (N!)

\(N!\) 的定义为： \[N! = N \times (N-1)! \quad \text{当 } N > 0 \text{ 时}\] \[0! = 1 \quad \text{(基本情况)}\]

伪代码（简化版）： 

FUNCTION Factorial(N: INTEGER) RETURNS INTEGER
    IF N = 0 THEN
        RETURN 1       <-- 基本情况
    ELSE
        RETURN N * Factorial(N - 1) <-- 递归步骤
    ENDIF
ENDFUNCTION

递归的追踪与回溯（栈的使用）

当调用函数时，系统会创建一个活动记录 (Activation Record)（或栈帧），用于存储局部变量、参数和返回地址。这些记录被压入调用栈 (Call Stack)（一种栈 ADT）。

  • 执行递归调用时，一个新的活动记录会被压入栈中。
  • 这一过程持续进行，直到达到基本情况。
  • 一旦触及基本情况，就开始回溯 (Unwinding)：栈顶函数调用的结果被返回，该活动记录随即被弹出。此过程向后持续进行，直到原始的函数调用返回最终结果。

编译器的任务： 编译器必须确保递归代码能正确管理调用栈，在执行和回溯过程中处理活动记录的压入和弹出。

递归的优势何在？

尽管任何递归算法都可以用迭代（使用循环）改写，但递归的优势在于它往往能产生更具优势的代码：

  • 更优雅： 对于复杂问题，特别是涉及树结构（如二叉树）或数学序列（如阶乘）的问题，递归表达得更自然、简洁。
  • 更易读/易证明： 对于本质上是递归的问题，代码直接反映了数学定义，从而更容易验证其正确性。

常见错误：忘记写基本情况！这会导致无限递归，并因栈内存溢出而导致程序崩溃。

19.2 学习小结

递归是用自身来定义函数。它非常强大，但必须有严格的基本情况以防止死循环。调用栈通过回溯过程管理执行流程和结果。


恭喜你完成了对算法和递归的深入探讨！这些确实是 A Level 的核心概念，构成了高级计算机科学的基石。继续练习追踪递归函数并计算大 O 复杂度吧——你一定能行！