# 算法设计与问题求解

> CIE A-Level 计算机科学 · 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u9-overview/
> 占比: n/a

本单元介绍用计算机解决问题的核心框架，涵盖计算思维、算法设计、标准查找/排序算法和算法跟踪，是9618所有编程工作的基础。

**先修:** 掌握9618编程基础和基本数据结构的预备知识

## 学习目标

- 运用核心计算思维原理分解现实问题
- 为常见问题类型设计正确、高效的算法
- 按照CIE 9618要求比较并实现标准查找与排序算法
- 跟踪调试现有算法以识别逻辑错误

## 单元概览

本单元遵循逻辑学习路径，从抽象思维原理逐步构建到具体算法实现。你将首先学习如何像计算机科学家一样思考，然后完整梳理端到端的问题求解流程，最后探索考试要求的常见算法类型和核心标准算法。

CIE 9618所有编程考核和试卷2的题目都依赖你在本单元构建的核心能力。掌握这些基础能让你之后遇到的所有进阶主题都更易理解和应用。

子主题按递进学习顺序排列如下：
- [计算思维基础](https://www.owlsprep.com/study/cie-9618-u9-computational-thinking-fundamentals/) — 涵盖分解、抽象、模式识别和核心算法设计原理。
- [问题求解流程](https://www.owlsprep.com/study/cie-9618-u9-problem-solving-process/) — 完整梳理将问题描述转化为可用算法的端到端工作流程。
- [算法分类](https://www.owlsprep.com/study/cie-9618-u9-algorithm-classification/) — 讲解如何按设计技术和性能特征对算法进行分类。
- [标准查找算法](https://www.owlsprep.com/study/cie-9618-u9-standard-searching-algorithms/) — 涵盖线性查找、二分查找及其实现和复杂度分析。
- [标准排序算法](https://www.owlsprep.com/study/cie-9618-u9-standard-sorting-algorithms/) — 讲解CIE 9618要求的冒泡排序、插入排序、归并排序和快速排序。
- [算法跟踪](https://www.owlsprep.com/study/cie-9618-u9-algorithm-tracing/) — 讲解如何逐步执行算法以测试正确性并识别逻辑错误。

## 常见错误

- **错误做法:** 在考试题目中混淆不同排序算法的时间复杂度和性质
  - 原因: 很多学生混淆稳定/不稳定排序，以及归并排序和快速排序的时间复杂度
  - 正确做法: 学习时制作一张汇总表，记录每个标准算法的复杂度和性质，方便复习
- **错误做法:** 在代码实现算法前跳过手动跟踪练习
  - 原因: 跟踪练习能培养系统化调试能力，这对笔试题目和实际编程都至关重要
  - 正确做法: 手动练习跟踪每个查找和排序算法的至少一个完整示例

## 速查表

| 概念 | 核心总结 |
| --- | --- |
| 分解 | 将大型问题拆分为更小的、可独立求解的子问题 |
| 抽象 | 隐藏无关细节，聚焦核心问题需求 |
| 线性查找时间复杂度 | 最好情况$O(1)$，平均/最坏情况$O(n)$ |
| 二分查找时间复杂度 | 最好情况$O(1)$，平均/最坏情况$O(\log n)$ |
| 冒泡排序时间复杂度 | 最好情况$O(n)$，平均/最坏情况$O(n^2)$ |
| 归并排序时间复杂度 | 所有情况$O(n \log n)$ |
| 快速排序时间复杂度 | 最好/平均情况$O(n \log n)$，最坏情况$O(n^2)$ |
| 算法跟踪 | 逐步执行算法以验证输出并识别逻辑错误 |

## 下一步

从下方第一个子主题开始学习，构建本单元其余内容所需的计算思维基础。完成9618第9单元所有子主题后，你可以进入下一个单元：数据结构，该单元直接建立在你在此学到的算法技能之上。

- [计算思维基础](https://www.owlsprep.com/zh/study/cie-9618-u9-computational-thinking-fundamentals/)
- [问题解决流程](https://www.owlsprep.com/zh/study/cie-9618-u9-problem-solving-process/)
- [算法分类](https://www.owlsprep.com/zh/study/cie-9618-u9-algorithm-classification/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u9-overview/