IB Computer Science: Algorithms Mastery Guide | IB 计算机：算法考点精讲

📚 IB Computer Science: Algorithms Mastery Guide | IB 计算机：算法考点精讲

Algorithms are the bedrock of computational thinking and problem-solving. In IB Computer Science, you need to understand not only what algorithms are, but also how to design, represent, trace, analyse and compare them. This article provides a comprehensive revision of the key algorithmic concepts required for the IB syllabus, including searching, sorting, efficiency and recursion, with precise explanations in both English and Chinese.

算法是计算思维和问题解决的基石。在 IB 计算机科学课程中，你不仅需要理解算法是什么，还要懂得如何设计、表示、追踪、分析以及比较它们。本文全面梳理了 IB 大纲要求的核心算法概念，包括搜索、排序、效率和递归，并以精准的中英双语进行讲解。

1. What is an Algorithm? | 什么是算法？

An algorithm is a finite sequence of well-defined, unambiguous instructions designed to solve a specific problem or perform a computation. It takes zero or more inputs, processes them step by step, and produces at least one output.

算法是一个有限序列，由定义清晰、无歧义的指令组成，旨在解决特定问题或执行计算。它接受零个或多个输入，逐步处理它们，并产生至少一个输出。

Every algorithm must satisfy five crucial properties: finiteness (it always terminates after a finite number of steps), definiteness (each step is precisely stated), input (it may accept data), output (it must produce a result), and effectiveness (each operation is basic enough to be carried out feasibly).

每个算法必须满足五个关键特性：有限性（总能在有限步骤后终止）、明确性（每个步骤都精确陈述）、输入（可以接受数据）、输出（必须产生结果）和有效性（每个操作都足够基本，可以切实执行）。

For example, a recipe for baking a cake is not strictly an algorithm in computer science because it may involve subjective steps like ‘mix until fluffy’. In contrast, Euclid’s algorithm for finding the greatest common divisor (GCD) is a perfect example: it is finite, unambiguous and always produces the correct GCD for any two positive integers.

例如，烘焙蛋糕的食谱在计算机科学中并不是严格意义上的算法，因为它可能涉及主观步骤，如“搅拌至蓬松”。相反，欧几里得用于求最大公约数的算法就是一个完美的例子：它有限、无歧义，并且对于任意两个正整数总能产生正确的 GCD。

2. Pseudocode and Flowcharts | 伪代码与流程图

Algorithms can be expressed in many ways, but the two most common forms in IB assessments are pseudocode and flowcharts. Pseudocode is a structured, human-readable description that resembles real programming languages like Java or Python, but omits strict syntax. It uses keywords such as IF...THEN...ELSE...ENDIF, WHILE...DO...ENDWHILE, and FOR...TO...NEXT.

算法可以用多种方式表达，但在 IB 评估中最常见的两种形式是伪代码和流程图。伪代码是一种结构化的、人类可读的描述，类似于 Java 或 Python 等真实编程语言，但省略了严格的语法。它使用诸如 IF...THEN...ELSE...ENDIF、WHILE...DO...ENDWHILE 以及 FOR...TO...NEXT 等关键词。

A flowchart uses geometric shapes to represent the flow of control. An oval denotes start or end; a rectangle indicates a process or calculation; a diamond represents a decision with a Boolean outcome (true/false); and arrows show the direction of flow. Flowcharts are excellent for visualising branching and looping structures.

流程图使用几何形状来表示控制流程。椭圆形表示开始或结束；矩形表示处理或计算；菱形表示具有布尔结果（真/假）的判断；箭头表示流程方向。流程图非常适合可视化分支结构和循环结构。

When writing pseudocode for IB exams, you must follow the approved notation. Use leftward arrow (←) for assignment, MOD for remainder, and DIV for integer division. Consistent indentation improves readability significantly.

在 IB 考试中编写伪代码时，你必须遵循批准的表示法。使用左箭头（←）表示赋值，MOD 表示取余，DIV 表示整数除法。一致的缩进能显著提高可读性。

// Pseudocode example: find maximum in array
MAX ← A[0]
FOR i ← 1 TO LENGTH(A)-1
    IF A[i] > MAX THEN
        MAX ← A[i]
    ENDIF
NEXT i
OUTPUT MAX

3. Linear Search | 线性搜索

Linear search is the simplest searching algorithm. It sequentially checks each element of a list until the target value is found or the list ends. It does not require the data to be sorted, making it suitable for unsorted datasets of any type.

线性搜索是最简单的搜索算法。它顺序检查列表中的每个元素，直到找到目标值或到达列表末尾。它不要求数据有序，因此适用于任何类型的无序数据集。

The algorithm uses a loop to iterate through an array. If the current element equals the target, the index is returned. If the loop finishes without finding the target, a failure indicator (often -1) is returned.

该算法使用循环遍历数组。如果当前元素等于目标值，则返回其索引。如果循环结束仍未找到目标，则返回一个失败指示符（通常为 -1）。

In the worst-case scenario (target is at the very end or not present), linear search examines all n elements, giving a time complexity of O(n). Its simplicity is its main advantage, but it becomes inefficient for large collections compared to binary search.

在最坏情况下（目标在最后或不存在），线性搜索会检查所有 n 个元素，时间复杂度为 O(n)。其主要优势在于简单，但与二分搜索相比，对大型集合效率较低。

Aspect	Linear Search
Precondition	None (works on unsorted data)
Time complexity (worst)	O(n)
Space complexity	O(1)

4. Binary Search | 二分搜索

Binary search is a much faster algorithm that operates on a sorted list. It repeatedly divides the search interval in half. By comparing the target with the middle element, it discards the half that cannot contain the target, drastically reducing the number of comparisons.

二分搜索是一种快得多的算法，作用于已排序列表。它反复将搜索区间对半分。通过比较目标与中间元素，丢弃不可能包含目标的那一半，从而大幅减少比较次数。

After each comparison, the search space is halved. The algorithm continues until the target is found or the low index exceeds the high index. This logarithmic behaviour gives binary search a worst-case time complexity of O(log n).

每次比较后，搜索空间减半。算法持续进行，直到找到目标或低索引超过高索引。这种对数行为使得二分搜索的最坏时间复杂度为 O(log n)。

A crucial prerequisite is that the array must be sorted. If data changes frequently, the cost of maintaining sorted order may reduce the net benefit. In IB exams, you are often required to trace binary search with a given dataset and state the number of comparisons made.

一个关键前提是数组必须已排序。如果数据频繁变动，维持有序性的开销可能会降低净收益。在 IB 考试中，你经常需要针对给定数据集追踪二分搜索过程，并说明比较次数。

// Pseudocode for iterative binary search
low ← 0
high ← length(A) - 1
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] == target THEN
        RETURN mid
    ELSE IF A[mid] < target THEN
        low ← mid + 1
    ELSE
        high ← mid - 1
    ENDIF
ENDWHILE
RETURN -1

5. Bubble Sort | 冒泡排序

Bubble sort is a simple comparison-based algorithm that repeatedly steps through a list, compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, indicating that the list is sorted.

冒泡排序是一种基于比较的简单算法，它反复遍历列表，比较相邻元素，如果顺序错误则交换它们。不断重复此过程，直到不再需要交换，表明列表已排序。

During each pass, the largest unsorted element 'bubbles' to its correct position at the end. The algorithm requires n-1 passes in the worst case, and each pass makes up to n-1 comparisons. Therefore, bubble sort has a worst-case and average time complexity of O(n²).

在每一趟遍历中，最大的未排序元素会“冒泡”到其末端的正确位置。该算法在最坏情况下需要 n-1 趟，每趟最多进行 n-1 次比较。因此，冒泡排序的最坏及平均时间复杂度为 O(n²)。

Bubble sort is adaptive: if the list is already sorted, it can detect this in one pass and terminate, giving a best-case time of O(n). Despite this, it is inefficient for large datasets and is primarily used for educational purposes to illustrate sorting concepts.

冒泡排序具有自适应性：如果列表已经有序，它可以在一次遍历中检测到并终止，最佳情况时间为 O(n)。尽管这样，它对大型数据集效率低下，主要用于教学，以阐明排序概念。

6. Selection Sort | 选择排序

Selection sort divides the input list into two parts: a sorted sublist at the front and an unsorted sublist that occupies the rest. Initially, the sorted part is empty. In each iteration, it finds the smallest (or largest) element in the unsorted sublist and swaps it with the leftmost unsorted element, expanding the sorted portion.

选择排序将输入列表分为两部分：前端已排序子列表，以及占据其余部分的未排序子列表。初始时排序部分为空。在每次迭代中，它会找到未排序子列表中的最小（或最大）元素，并将其与最左边的未排序元素交换，从而扩大已排序部分。

This algorithm performs exactly n-1 swaps, which is an advantage over bubble sort when write operations are costly. However, the number of comparisons remains O(n²) regardless of the initial order. Selection sort is not stable (it may change the relative order of equal elements) and does not adapt to partially sorted data.

该算法恰好执行 n-1 次交换，当写操作昂贵时，这是相对于冒泡排序的一个优势。但无论初始顺序如何，比较次数始终为 O(n²)。选择排序不是稳定的（可能改变相等元素的相对顺序），并且不能自适应部分有序的数据。

Its time complexities: best-case O(n²), average-case O(n²), worst-case O(n²). Space complexity is O(1) because it operates in-place.

其时间复杂度：最佳情况 O(n²)，平均情况 O(n²)，最坏情况 O(n²)。空间复杂度为 O(1)，因为它原地操作。

7. Insertion Sort | 插入排序

Insertion sort builds the sorted list one element at a time, mimicking the way many people sort playing cards. It takes each element from the unsorted part and inserts it into its correct position within the already sorted portion, shifting larger elements to the right as necessary.

插入排序一次一个元素地构建有序列表，模仿许多人整理扑克手牌的方式。它从无序部分逐个取出元素，并将其插入已排序部分的正确位置，必要时将较大的元素向右移动。

This algorithm is efficient for small datasets and excels when the input is nearly sorted (best-case time O(n) if the array is already sorted). In the worst and average scenarios, each insertion may require shifting many elements, leading to O(n²) time complexity.

该算法对小型数据集非常高效，并且当输入近乎有序时表现突出（如果数组已排序，最佳情况时间为 O(n)）。在最坏和平均情况下，每次插入可能需要移动大量元素，导致 O(n²) 的时间复杂度。

Insertion sort is stable and in-place. Its O(n²) behaviour is acceptable when n is small, and it often outperforms more complex algorithms like quicksort for tiny arrays.

插入排序是稳定的且是原地排序。当 n 很小时，其 O(n²) 的行为是可以接受的，并且对于微型数组，它常常优于快速排序等更复杂的算法。

// Insertion sort pseudocode
FOR i ← 1 TO length(A)-1
    key ← A[i]
    j ← i - 1
    WHILE j >= 0 AND A[j] > key DO
        A[j+1] ← A[j]
        j ← j - 1
    ENDWHILE
    A[j+1] ← key
NEXT i

8. Introduction to Big O Notation | 大 O 表示法入门

Big O notation provides a mathematical way to describe the upper bound of an algorithm's time or space requirements as the input size n grows. It focuses on the dominant term and ignores constant factors, giving a high-level picture of scalability.

大 O 表示法提供了一种数学方法，用于描述随着输入规模 n 增长，算法在时间或空间需求上的上限。它关注主导项并忽略常数因子，从高层次描述可扩展性。

Common complexity classes you must know for IB include: O(1) (constant time, e.g. accessing an array element by index), O(log n) (logarithmic, e.g. binary search), O(n) (linear, e.g. linear search), O(n log n) (linearithmic, e.g. merge sort), O(n²) (quadratic, e.g. bubble sort), and O(2ⁿ) (exponential, e.g. recursive Fibonacci without memoisation).

IB 课程中你必须掌握的常见复杂度类别包括：O(1)（常数时间，例如通过索引访问数组元素）、O(log n)（对数时间，例如二分搜索）、O(n)（线性时间，例如线性搜索）、O(n log n)（线性对数时间，例如归并排序）、O(n²)（平方时间，例如冒泡排序）以及 O(2ⁿ)（指数时间，例如无记忆化的递归斐波那契）。

To determine Big O, count the primitive operations as a function of n and then identify the fastest-growing term. For example, a loop that runs n times inside another loop that also runs n times gives n × n = n² operations, so the complexity is O(n²).

要确定大 O 复杂度，先将基本操作的次数表示为 n 的函数，然后识别增长最快的项。例如，一个循环运行 n 次，其内部还有一个同样运行 n 次的循环，总共 n × n = n² 次操作，因此复杂度为 O(n²)。

Efficiency ranking (best to worst): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

9. Recursion Fundamentals | 递归基础

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. Every recursive solution must have a base case (a condition that stops the recursion) and a recursive step that moves towards the base case. Without a proper base case, infinite recursion and stack overflow occur.

递归是一种技术，其中函数调用自身来解决同一问题的更小实例。每个递归解决方案都必须有一个基本情况（停止递归的条件），以及一个朝着基本情况推进的递归步骤。没有合适的基本情况，会导致无限递归和栈溢出。

A classic example is calculating the factorial of n: fact(n) = n × fact(n-1), with base case fact(0) = 1. Another is the Fibonacci sequence, though naive recursive Fibonacci has exponential complexity O(2ⁿ) because it recomputes overlapping subproblems many times.

一个经典例子是计算 n 的阶乘：fact(n) = n × fact(n-1)，基本情况 fact(0) = 1。另一个例子是斐波那契数列，不过朴素的递归斐波那契具有指数复杂度 O(2ⁿ)，因为它多次重复计算重叠的子问题。

Recursion uses a call stack to keep track of function calls. Each recursive call adds a new frame to the stack, which can consume significant memory for deep recursions. This is why iterative solutions are sometimes preferred for space efficiency.

递归使用调用栈来跟踪函数调用。每递归调用一次都会向栈中添加一个新帧，对于深层递归会消耗大量内存。这就是为什么有时迭代解决方案在空间效率上更受青睐。

IB exams may ask you to trace a recursive function step by step, showing the call stack and the return values. Understanding how the stack unwinds is essential.

IB 考试可能会要求你逐步追踪递归函数，展示调用栈和返回值。理解栈如何展开是至关重要的。

10. Algorithm Comparison and Tracing | 算法比较与追踪

Tracing an algorithm involves manually simulating its execution with a specific set of inputs. You record variable changes, loop iterations, and outputs at each step. IB assessments frequently include trace table questions where you fill in the values of variables as the algorithm executes.

追踪算法涉及用一组特定输入手动模拟其执行过程。你记录每一步的变量变化、循环迭代和输出。IB 评估中经常包含追踪表问题，你需要在算法执行时填写变量的值。

When comparing algorithms, consider not only time complexity but also space complexity, stability (does it preserve the relative order of equal elements?), adaptivity (does it perform better on partially sorted data?), and implementation simplicity.

比较算法时，不仅要考虑时间复杂度，还要考虑空间复杂度、稳定性（是否保持相等元素的相对顺序？）、自适应性（对部分有序数据表现是否更好？）以及实现简洁性。

For searching, choose linear search when the data is unsorted or small; choose binary search when the data is sorted and large. For sorting, insertion sort shines for small or nearly sorted arrays; merge sort guarantees O(n log n) but requires extra space; quicksort is generally fast but has a worst case of O(n²).

对于搜索，当数据无序或规模较小时选择线性搜索；当数据已排序且规模大时选择二分搜索。对于排序，插入排序在小型或近乎有序的数组上表现出色；归并排序能保证 O(n log n) 但需要额外空间；快速排序通常很快但最坏情况为 O(n²)。

The following table summarises the key algorithmic categories you are expected to master for the IB Computer Science exam.

下表总结了你需要为 IB 计算机科学考试掌握的关键算法类别。

Algorithm Type	Example	Best Time	Average Time	Worst Time
Search (unsorted)	Linear search	O(1)	O(n)	O(n)
Search (sorted)	Binary search	O(1)	O(log n)	O(log n)
Simple sort	Bubble sort	O(n)	O(n²)	O(n²)
Simple sort	Selection sort	O(n²)	O(n²)	O(n²)
Simple sort	Insertion sort	O(n)	O(n²)	O(n²)
Efficient sort	Merge sort	O(n log n)	O(n log n)	O(n log n)

Published by TutorHao | IB Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

IB Computer Science: Algorithms Mastery Guide | IB 计算机：算法考点精讲