Using and Understanding Algorithms | 使用与理解算法

📚 Using and Understanding Algorithms | 使用与理解算法

Algorithms are at the heart of computer science. An algorithm is a precise sequence of steps that solves a problem or completes a task. In Edexcel A-Level Computer Science, you must be able to read, trace, design and compare algorithms, using standard tools such as pseudocode, trace tables and Big O notation.

算法是计算机科学的核心。算法是解决问题或完成任务的一系列精确定义的步骤。在 Edexcel A-Level 计算机科学中，你必须能够阅读、跟踪、设计和比较算法，并使用伪代码、跟踪表和 Big O 表示法等标准工具。

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

An algorithm is a finite sequence of unambiguous steps that can be carried out to solve a problem or complete a task. It takes inputs, processes them, and produces outputs. The same algorithm can be implemented in many programming languages, but the logic remains unchanged.

算法是有穷的、无歧义的步骤序列，用于解决一个问题或完成一项任务。它接收输入、处理输入并产生输出。同一个算法可以用多种编程语言实现，但逻辑保持不变。

Five important properties are usually required: finiteness, definiteness, input, output, and effectiveness. Finiteness means the algorithm must stop after a limited number of steps. Definiteness means each step must be clear and unambiguous. Effectiveness means each step must be simple enough to be executed in finite time.

通常需要五个重要性质：有穷性、确定性、输入、输出和可行性。有穷性意味着算法必须在有限步之后停止。确定性意味着每个步骤必须清晰且无歧义。可行性意味着每一步都足够简单，可以在有限时间内执行。

2. Representing Algorithms: Pseudocode and Flowcharts | 算法表示：伪代码与流程图

Before coding, algorithms are often represented in pseudocode or as flowcharts. Pseudocode is a structured, language-independent way of describing instructions using keywords such as INPUT, OUTPUT, IF, THEN, ELSE, WHILE, FOR and ENDWHILE. It lets you focus on logic without syntax errors.

在编写代码之前，算法通常用伪代码或流程图表示。伪代码是一种结构化、与编程语言无关的描述方式，使用 INPUT、OUTPUT、IF、THEN、ELSE、WHILE、FOR 和 ENDWHILE 等关键字。它能让你专注于逻辑而不必担心语法错误。

Flowcharts use standard symbols: an oval for start and stop, a rectangle for a process, a parallelogram for input/output, and a diamond for a decision. Arrows show the flow of control from one step to the next.

流程图使用标准符号：椭圆表示开始和结束，矩形表示处理，平行四边形表示输入/输出，菱形表示判断。箭头表示控制从一个步骤到下一个步骤的流向。

3. The Three Building Blocks: Sequence, Selection, Iteration | 三种基本结构：顺序、选择与迭代

Every algorithm can be built from three control structures. Sequence is the default: instructions are executed one after another in the order written. Selection chooses between different paths, typically using IF…THEN…ELSE or CASE statements. Iteration repeats a block of code using WHILE loops, FOR loops or REPEAT…UNTIL loops.

每个算法都可以由三种控制结构构建。顺序是默认结构：指令按照书写顺序一条接一条执行。选择使用 IF…THEN…ELSE 或 CASE 语句在不同路径之间进行选择。迭代使用 WHILE 循环、FOR 循环或 REPEAT…UNTIL 循环重复代码块。

These structures are sufficient to express any computable function. This is one consequence of the structured program theorem and supports the use of modular design.

这些结构足以表达任何可计算的函数。这是结构化程序定理的一个结论，并支持模块化设计的使用。

4. Trace Tables and Dry Runs | 跟踪表与手工执行

A trace table records the values of variables, inputs, outputs and conditions as each line of pseudocode is executed. A dry run is the manual process of working through an algorithm using a trace table. This helps find logical errors before coding.

跟踪表记录伪代码每一行执行时变量、输入、输出和条件的值。手工执行是使用跟踪表手动运行算法的过程。这有助于在编码之前发现逻辑错误。

When completing a trace table, add a column for each variable and a column for any output. Update values line by line. For iterative algorithms, include a column for the loop condition so you can see when the loop ends.

完成跟踪表时，为每个变量添加一列，并为任何输出添加一列。逐行更新数值。对于迭代算法，为循环条件添加一列，以便查看循环何时结束。

5. Linear Search | 线性搜索

Linear search checks each item in a list in order, from the first element to the last, until the target is found or the list ends. It does not require the list to be sorted. In pseudocode, a FOR or WHILE loop compares each element with the search key.

线性搜索按顺序检查列表中的每一项，从第一个元素到最后一个元素，直到找到目标或列表结束。它不要求列表有序。在伪代码中，FOR 或 WHILE 循环将每个元素与搜索关键字进行比较。

In the worst case, linear search makes n comparisons for a list of n items, so its time complexity is O(n). It is simple and works on any list, but it is inefficient for large datasets.

在最坏情况下，线性搜索对包含 n 项的列表进行 n 次比较，因此它的时间复杂度为 O(n)。它简单且适用于任何列表，但对于大数据集效率较低。

6. Binary Search | 二分查找

Binary search works on a sorted list. It repeatedly finds the middle element, compares it with the target, and discards half of the remaining list. If the middle value is too low, the target must be in the upper half; if too high, in the lower half.

二分查找在有序列表上工作。它反复找到中间元素，将其与目标进行比较，并丢弃剩余列表的一半。如果中间值太低，目标一定在上半部分；如果太高，则在下半部分。

Each comparison halves the search space, so the maximum number of comparisons is about log₂ n + 1. Binary search has a time complexity of O(log n), making it far faster than linear search for large sorted lists.

每次

Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

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