计算思维与算法导论 / Introduction to Computational Thinking and Algorithms

计算思维：从厨房到宇宙的隐形算法

中文阐释

当你按照食谱烘焙蛋糕时，每一步——预热烤箱、混合原料、设定时间——都是精确的指令序列。食谱的本质就是一个算法：它接受输入（面粉、鸡蛋等），通过明确步骤处理，最终输出可食用的蛋糕。同样，使用地图App导航时，算法在数百万条道路中计算最短路径；刷短视频时，推荐算法根据你的历史行为预测下一个可能喜欢的视频。这些场景共同揭示了一个核心概念：计算思维（Computational Thinking），即运用计算机科学的基本原理（如分解、模式识别、抽象和算法设计）来解决问题、设计系统和理解人类行为的一种思维模式。它并非程序员的专属技能，而是数字时代每个人的基础素养，如同读、写、算一样重要。本章将带你探索算法与数据结构的基石，理解它们为何是现代科技的隐形骨架，并预览全书的学习路径。

English Exploration

When you follow a recipe to bake a cake, each step—preheating the oven, mixing ingredients, setting a timer—is a precise sequence of instructions. At its core, a recipe is an algorithm: it takes inputs (flour, eggs, etc.), processes them through defined steps, and produces an output (an edible cake). Similarly, when a map app calculates the fastest route through millions of roads, an algorithm is at work; when a short-video platform recommends your next clip, a recommendation algorithm analyzes your history to predict what you might like. These scenarios reveal a central concept: Computational Thinking—a problem-solving approach that applies fundamental principles of computer science (such as decomposition, pattern recognition, abstraction, and algorithmic design) to understand and shape the world. It is not just for programmers; it is a fundamental literacy for the digital age, as essential as reading, writing, and arithmetic. This chapter will guide you through the foundations of algorithms and data structures, explain why they are the invisible skeleton of modern technology, and outline the journey ahead in this book.

---

算法的本质：解决问题的步骤艺术

中文阐释

算法（Algorithm）是解决特定问题或执行特定任务的一系列清晰、有限的步骤。它像一份详尽的“操作手册”，无论谁按照顺序执行，都能在有限时间内得到相同结果。算法的核心特征包括：

• **输入**（Input）：零个或多个外部提供的数据。
• **输出**（Output）：至少一个处理后的结果。
• **明确性**（Definiteness）：每一步骤必须无歧义。
• **有限性**（Finiteness）：必须在有限步骤后终止。
• **有效性**（Effectiveness）：每一步都应可行，能用基本操作实现。

例如，欧几里得算法求两个正整数的最大公约数（GCD）： 1. 输入两个数 $a$ 和 $b$（假设 $a > b$）。 2. 用 $a$ 除以 $b$，得到余数 $r$。 3. 如果 $r = 0$，则 $b$ 就是 GCD；否则，令 $a = b$，$b = r$，重复步骤 2。 这个算法仅用除法和取余，就能高效解决古老数学问题。再如二分查找（Binary Search）：在有序数组中查找目标值，每次将搜索范围减半，直到找到或确认不存在。它比逐个检查的线性查找（Linear Search）快得多，尤其当数据量庞大时。

算法不仅是计算机的专利，也渗透于日常生活：

• **食谱**：输入食材，输出菜肴。
• **乐高拼装说明书**：一步步组装模型。
• **解魔方公式**：一系列旋转操作还原混乱。
• **课堂课表**：安排每天课程的顺序。

这些例子说明，算法思维帮助我们分解问题（decomposition）、识别模式（pattern recognition）、抽象细节（abstraction）和设计步骤（algorithm design）——这正是计算思维的四大支柱。

English Exploration

An algorithm is a finite sequence of well-defined, unambiguous instructions to solve a specific problem or perform a task. It acts like a detailed “instruction manual”: anyone following the steps in order will arrive at the same result within a finite time. Core characteristics include:

• **Input**: Zero or more externally provided data.
• **Output**: At least one resulting value.
• **Definiteness**: Each step must be clear and unambiguous.
• **Finiteness**: The algorithm must terminate after a finite number of steps.
• **Effectiveness**: Every step should be feasible with basic operations.

Consider Euclid’s algorithm for finding the greatest common divisor (GCD) of two positive integers: 1. Input two numbers $a$ and $b$ (assume $a > b$). 2. Divide $a$ by $b$ to get remainder $r$. 3. If $r = 0$, then $b$ is the GCD; else, set $a = b$, $b = r$, and repeat step 2. This algorithm solves an ancient mathematical problem efficiently using only division and modulus. Another example is binary search: in a sorted array, it repeatedly halves the search range until the target is found or confirmed absent. It is much faster than linear search—checking each element one by one—especially with large datasets.

Algorithms are not exclusive to computers; they permeate daily life:

• **Recipes**: transform ingredients into dishes.
• **LEGO assembly manuals**: step-by-step model construction.
• **Rubik’s Cube formulas**: sequences of rotations to restore order.
• **Class schedules**: ordering daily lessons.

These examples illustrate how algorithmic thinking helps us decompose problems, recognize patterns, abstract details, and design steps—the four pillars of computational thinking.

---

数据结构：信息的组织智慧

中文阐释

如果说算法是“动作的步骤”，那么数据结构（Data Structure）就是“信息的组织方式”。它定义了数据如何存储、关联和访问，直接影响算法的效率。选择合适的数据结构，如同为工具选择合适的工具箱——用错了会事倍功半。

为什么数据结构如此重要？

想象图书馆的书架：如果书籍随机堆放（无结构），找一本特定书需遍历所有书（$O(n)$ 时间）；如果按字母顺序排列在书架上（有序数组），可用二分查找快速定位（$O(\log n)$ 时间）。数据结构决定了数据操作的效率。

基本数据结构及其应用

1. 数组（Array）：连续内存存储的同类型元素集合。支持随机访问（通过索引立即获取元素），但插入/删除需移动后续元素（$O(n)$ 时间）。

• *例子*：成绩列表、像素矩阵。

2. 链表（Linked List）：元素（节点）通过指针链接，不保证连续存储。插入/删除高效（$O(1)$ 若已知位置），但访问需从头遍历（$O(n)$）。

• *例子*：音乐播放列表（下一首链接）、区块链。

3. 栈（Stack）：后进先出（LIFO）结构，仅允许在顶部 push/pop。

• *例子*：浏览器后退按钮、函数调用堆栈。

4. 队列（Queue）：先进先出（FIFO）结构，元素从尾部进入、头部离开。

• *例子*：打印任务队列、消息缓冲。

5. 树（Tree）：分层结构，根节点向下分支。二叉树每个节点最多两个子节点；二叉搜索树左子节点小于父、右子节点大于父，支持高效查找（平均 $O(\log n)$）。

• *例子*：文件系统目录、DOM 树、决策过程。

6. 图（Graph）：顶点（节点）通过边连接，表示关系网络。可用于建模社交网络、地图路线。

• *例子*：朋友圈关系、地铁线路。

```mermaid graph TD A[数组: 连续存储] --> B[随机访问 O(1)] A --> C[插入/删除 O(n)] D[链表: 指针链接] --> E[插入/删除 O(1)] D --> F[访问 O(n)] G[栈: LIFO] --> H[后退按钮] I[队列: FIFO] --> J[打印队列] K[树: 分层] --> L[文件系统] M[图: 网络] --> N[社交网络] ```

数据结构与算法的共生关系

算法和数据结构如车之两轮。例如，深度优先搜索（DFS）算法在图结构上遍历；快速排序算法依赖数组的随机访问。错误的选择会导致性能灾难：用链表存储需频繁随机访问的数据，或数组存储频繁插入的数据，都会显著降低效率。因此，优秀程序员不仅设计算法，更精心选择数据结构。

English Exploration

If algorithms are the “steps of action,” then data structures are the “organization of information.” They define how data is stored, related, and accessed, directly impacting algorithmic efficiency. Choosing the right data structure is like selecting the proper toolbox for a job—using the wrong one can halve your productivity.

Why Are Data Structures So Important?

Consider a library shelf: if books are piled randomly (no structure), finding a specific title requires scanning all books ($O(n)$ time); if arranged alphabetically (sorted array), binary search locates it quickly ($O(\log n)$ time). Data structures dictate the efficiency of data operations.

Fundamental Data Structures and Applications

1. Array: Contiguous memory storage of elements of the same type. Supports random access (immediate retrieval via index), but insertion/deletion requires shifting subsequent elements ($O(n)$ time).

• *Example*: grade lists, pixel matrices.

2. Linked List: Elements (nodes) connected by pointers, not necessarily contiguous. Efficient insertion/deletion ($O(1)$ if position known), but access requires traversal from head ($O(n)$).

• *Example*: music playlists (next-track links), blockchains.

3. Stack: Last-In-First-Out (LIFO) structure; push/pop only at top.

• *Example*: browser back buttons, function call stacks.

4. Queue: First-In-First-Out (FIFO) structure; elements enter at rear, exit at front.

• *Example*: print job queues, message buffers.

5. Tree: Hierarchical structure with root branching downward. A binary tree has at most two children per node; a binary search tree has left child < parent < right child, enabling efficient search (average $O(\log n)$).

• *Example*: file system directories, DOM trees, decision processes.

6. Graph: Vertices (nodes) connected by edges, representing relational networks. Models social networks, transit maps.

• *Example*: friend circles, subway lines.

```mermaid graph TD A[Array: contiguous] --> B[random access O(1)] A --> C[insert/delete O(n)] D[Linked List: pointers] --> E[insert/delete O(1)] D --> F[access O(n)] G[Stack: LIFO] --> H[back button] I[Queue: FIFO] --> J[print queue] K[Tree: hierarchical] --> L[file system] M[

算法复杂度：效率的度量尺

中文阐释

当我们说一个算法“快”或“慢”时，实际是在讨论其时间复杂度——执行时间随输入规模增长的变化趋势。大O表示法（Big O Notation）正是描述这种增长趋势的数学工具，它关注最坏情况下的上界，忽略常数因子和低阶项。例如，若算法执行时间为 $T(