📚 Algorithm Essentials for IB & CIE Computer Science | IB CIE 计算机：算法 考点精讲
Algorithms form the very heartbeat of computer science. In both IB and CIE curricula, a solid grasp of algorithmic thinking is not only essential for problem-solving questions but also underpins every topic from data structures to system design. This article distils the core concepts you must master, covering fundamental definitions, ways to represent algorithms, classic searching and sorting routines, and the basics of efficiency analysis using Big O notation.
算法是计算机科学跳动的脉搏。在 IB 和 CIE 课程中，扎实掌握算法思维不仅是解决实际问题题目的关键，也支撑着从数据结构到系统设计的每个主题。本文将提炼你必须掌握的核心概念，涵盖基本定义、算法表示方式、经典的搜索与排序例程，以及使用大 O 表示法进行效率分析的基础。
1. What Is an Algorithm? | 什么是算法？
An algorithm is a well-defined, step-by-step procedure for solving a problem or accomplishing a task. It must be finite (completing after a limited number of steps), precise (each step is unambiguous), and effective (each step can be carried out in practice). Input and output are also fundamental: an algorithm takes zero or more inputs and produces at least one output.
算法是一个定义明确的、逐步解决问题的过程或完成任务的方法。它必须是有限的（在有限步骤后结束）、精确的（每一步都无歧义）且有效的（每一步都是实际可执行的）。输入和输出同样基本：算法接收零个或多个输入，并产生至少一个输出。
2. Representing Algorithms: Pseudocode and Flowcharts | 算法表示：伪代码与流程图
On paper, you will frequently encounter two formal ways to describe an algorithm: pseudocode and flowcharts. Pseudocode uses structured English-like statements that resemble programming code but ignore language-specific syntax. It allows you to focus on the logic using keywords such as IF, THEN, ELSE, WHILE, FOR, OUTPUT. Flowcharts, on the other hand, use standardized symbols—ovals for start/stop, parallelograms for input/output, rectangles for processes, diamonds for decisions—connected by arrows to show the flow of control.
在纸面上，你经常会遇到两种正式描述算法的方式：伪代码和流程图。伪代码使用结构化的、类似英语的语句，摹仿编程代码但忽略特定语言的语法，让你能够通过 IF、THEN、ELSE、WHILE、FOR、OUTPUT 等关键词专注逻辑。流程图则使用标准化符号——椭圆形表示开始/结束，平行四边形表示输入/输出，矩形表示处理过程，菱形表示判断——并通过箭头连接来展示控制流。
3. Sequence, Selection, Iteration – The Building Blocks | 顺序、选择、循环 —— 构建块
Every algorithm can be constructed from three basic control structures: sequence (executing steps one after another), selection (branching based on a condition, typically IF-ELSE), and iteration (repeating a block of code using WHILE, REPEAT-UNTIL, or FOR loops). IB and CIE exam questions often ask you to trace or write code that combines these structures to achieve a specific goal.
每一个算法都可以由三种基本控制结构构建：顺序（按次序执行步骤）、选择（根据条件分支，通常是 IF-ELSE）和迭代（使用 WHILE、REPEAT-UNTIL 或 FOR 循环重复代码块）。IB 和 CIE 的考题经常要求你追踪或编写结合这些结构以实现特定目标的代码。
4. Linear Search | 线性搜索
Linear search (or sequential search) checks each element of a list in turn until a match is found or the list ends. It works on unsorted data and is simple to implement. In pseudocode, a typical WHILE loop increments an index until the target is located or the index exceeds the array length. Its worst-case and average-case time complexity is O(n), where n is the number of items. Always remember to handle the “not found” scenario by outputting an appropriate message or returning a sentinel value like -1.
线性搜索（或称顺序搜索）依次检查列表中的每个元素，直到找到匹配项或列表结束。它适用于未排序的数据，且实现简单。在伪代码中，典型的 WHILE 循环递增索引，直到找到目标或索引超出数组长度。其最坏情况和平均情况的时间复杂度为 O(n)，其中 n 为元素个数。请务必记住通过输出恰当的讯息或返回如 -1 的标志值来处理“未找到”的情况。
5. Binary Search | 二分搜索
Binary search is a far more efficient algorithm, but it requires the data to be sorted beforehand. It repeatedly divides the search interval in half: compare the target with the middle element; if it matches, the search ends; if the target is smaller, continue searching in the left half; otherwise, in the right half. The maximum number of comparisons is roughly log₂n, giving a time complexity of O(log n). Exam questions frequently ask you to trace the values of low, high, and mid pointers through each iteration, so practice with small arrays of numbers.
二分搜索是一种高效得多的算法，但要求数据预先排好序。它反复将搜索区间分成两半：将目标与中间元素比较；如果匹配，搜索结束；如果目标较小，则在左半部分继续搜索；否则，在右半部分。最大比较次数约为 log₂n，时间复杂度为 O(log n)。考试题目经常要求你跟踪每轮迭代中 low、high 和 mid 指针的值，因此请用小数组多加练习。
6. Bubble Sort | 冒泡排序
Bubble sort repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. The largest unsorted element “bubbles up” to its correct position at the end of each pass. A flag can be used to detect whether any swap occurred; if no swaps occur in a pass, the list is already sorted and the algorithm can terminate early. The worst-case and average-case time complexity is O(n²). Although simple, it is often examined because it illustrates the swapping technique and nested loops clearly.
冒泡排序反复遍历列表，比较相邻的元素，如果次序错误就交换它们。每一轮遍历后，最大的未排序元素会“冒泡”到其正确的位置。可以使用一个标志来检测是否发生了交换；如果一轮遍历中没有发生交换，说明列表已经有序，算法可以提前终止。最坏情况和平均情况的时间复杂度为 O(n²)。虽然简单，但因清晰展示了交换技术和嵌套循环，它经常被考查。
7. Selection Sort | 选择排序
Selection sort improves on bubble sort by reducing the number of swaps. In each pass, it finds the smallest (or largest) element in the unsorted portion and swaps it with the element at the beginning of that portion. After k passes, the first k elements are in their final sorted positions. The number of comparisons remains O(n²), but the number of swaps is at most n-1. Students often confuse selection sort with bubble sort; remember that selection sort does one swap per pass, whereas bubble sort may perform many.
选择排序通过减少交换次数改进了冒泡排序。在每一轮中，它找到未排序部分中的最小（或最大）元素，并将其与该部分起始位置的元素交换。经过 k 轮后，前 k 个元素已处于最终的排序位置。比较次数仍为 O(n²)，但交换次数最多为 n-1。学生常将选择排序与冒泡排序混淆；请记住，选择排序每轮只进行一次交换，而冒泡排序可能进行多次。
8. Insertion Sort | 插入排序
Insertion sort builds the final sorted array one item at a time. It considers one element at a time and inserts it into its correct position within the already sorted left portion, shifting larger elements to the right as necessary. It resembles the way people sort a hand of playing cards. Insertion sort is efficient for small data sets and is stable. In the best case (already sorted data), it runs in O(n) time; average and worst case are O(n²). Exam tracing questions typically ask you to show the array after each “insertion” step.
插入排序一次一个元素地构建最终排序数组。它每次考虑一个元素，并将其插入到已排序左部分的正确位置，必要时将较大元素向右移动。这类似于人们整理一手扑克牌的方式。插入排序对小数据集高效且是稳定的。在最好情况下（数据已排序），运行时间为 O(n)；平均和最坏情况为 O(n²)。考试追踪题通常会要求你展示每次“插入”步骤后的数组。
9. Algorithm Efficiency and Big O Notation | 算法效率与大O表示法
Big O notation describes how the run time or memory usage of an algorithm scales with the size of the input. It gives an upper bound on the growth rate. Common complexities in ascending order: O(1) (constant), O(log n) (logarithmic), O(n) (linear), O(n log n) (linearithmic), O(n²) (quadratic), O(2ⁿ) (exponential). You must be able to identify these by inspecting nested loops (e.g., two nested loops iterating n times each suggest O(n²)) and by recognising algorithms like binary search (O(log n)). Always focus on the dominant term and ignore constants.
大O表示法描述了算法的运行时间或内存使用量随输入规模增长的情况，它给出了增长速率的上限。常见的复杂度按升序排列为：O(1)（常数）、O(log n)（对数）、O(n)（线性）、O(n log n)（线性对数）、O(n²)（平方）、O(2ⁿ)（指数）。你必须能够通过检查嵌套循环（例如，两个各迭代 n 次的嵌套循环暗示 O(n²)）以及识别二分搜索这类算法（O(log n)）来确定复杂度。始终关注主导项并忽略常数。
10. Choosing the Right Algorithm – Trade-offs | 选择合适的算法——权衡
No single algorithm is universally best. The choice depends on data size, whether the data is already sorted, memory constraints, and stability requirements. For small, nearly sorted datasets, insertion sort may outperform quicksort (which you may encounter beyond IGCSE/AS). For searching, binary search is far faster than linear search but demands pre-sorted data. IB and CIE like to ask you to justify your choice, so always connect your reasoning to the context given in the question.
没有一种算法是万能的。选择取决于数据规模、数据是否已排序、内存限制以及稳定性要求。对于小而接近有序的数据集，插入排序可能优于快速排序（可能在 IGCSE/AS 之外遇到）。对于搜索，二分搜索远快于线性搜索，但要求数据预先排序。IB 和 CIE 喜欢让你论证选择，因此请始终将推理与题目给出的情境联系起来。
11. Tracing Algorithms – A Key Exam Skill | 追踪算法——关键考试技能
Tracing (or dry running) an algorithm involves manually stepping through the code line by line with sample input and recording the values of variables at each stage. Use a trace table with columns for each variable and output. This skill is tested heavily. When tracing, be systematic: update the table after each statement. Pay special attention to loop conditions and boundary cases (first iteration, last iteration). Always double-check whether an array index starts at 0 or 1, as per the exam convention.
追踪（或称手动运行）算法意味着使用示例输入逐行执行代码，并记录每一阶段变量的值。使用包含各变量和输出的列的追踪表。这项技能考查频繁。追踪时要有条理：在每条语句后更新表格。特别注意循环条件和边界情况（第一次迭代、最后一次迭代）。务必根据考试惯例，反复核对数组索引是从 0 还是 1 开始。
12. Writing Algorithms from Scratch – Exam Tips | 从零编写算法——应试技巧
In paper-based coding questions, clarity trumps cleverness. Use simple, readable pseudocode with proper indentation. Name variables meaningfully (e.g., index, maxValue). Always initialise counters and accumulators. Include comments to explain your logic. Test your algorithm mentally with a small input to catch off-by-one errors. Remember to specify preconditions (e.g., “array is sorted”) if your algorithm depends on them. And never forget to output the result.
在书面编码题中，清晰胜于巧妙。使用简单、可读的伪代码，并正确缩进。变量命名要有意义（例如 index、maxValue）。务必初始化计数器和累加器。加入注释来解释你的逻辑。用一个小输入在脑中测试你的算法，以捕获差一错误。如果你的算法依赖于前提条件（例如，“数组已排序”），请务必说明。永远不要忘记输出结果。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导