第14章算法基础

📚 本章课程

课程	内容
14.1 算法的特性	—
14.2 时间复杂度与空间复杂度 (2课时)	—
14.2.1 时间复杂度与空间复杂度-01	复杂度的基本概念
14.2.2 时间复杂度与空间复杂度-02	复杂度分析方法
14.3.1 算法策略知识点概述	—
14.3.2 算法策略概述	—
14.3.3 分治法	—
14.3.4 贪心法	—
14.3.5 动态规划法	—
14.3.6 回溯法	—
14.4.1 查找算法知识点概述	—
14.4.2 顺序查找	—
14.4.3 二分查找	—
14.4.4 哈希散列表	—
14.5.1 排序算法知识点概述	—
14.5.2 排序的基本概念	—
14.5.3 插入类排序	—
14.5.4 选择类排序	—
14.5.6 归并排序	—
14.5.7 基数排序	—
14.5.8 排序算法对比	—
14.6 章节概述	知识点梳理和重点回顾
14.7 章节回顾	典型题目分析和解题技巧
14.6 算法基础章节概述	对第14章进行体系化梳理，打通知识结构与命题逻辑，形成可执行的复习路线图。
14.7 算法基础章节回顾	对第14章进行考点复盘、错因归类与冲刺训练设计，帮助建立稳定得分能力。

📚 章节概述

算法基础是软考中级软件设计师考试的重要内容，涵盖算法的基本概念、复杂度分析、算法策略和经典算法。本章将系统学习算法设计和分析的基本方法。

🎯 学习目标

通过本章学习，你将掌握：

算法的基本概念和特性
时间复杂度和空间复杂度分析
常用算法设计策略
查找和排序算法的原理
算法效率的分析和比较

📖 课程安排

14.1-14.2 算法基础概念 (4课时)

14.1 算法的特性

算法定义 - 解决问题的有限步骤序列
算法特性
- 有穷性：算法必须在有限步骤内结束
- 确定性：每一步都有确切的定义
- 输入：有零个或多个输入
- 输出：有一个或多个输出
- 可行性：每一步都是可执行的

14.2 时间复杂度与空间复杂度 (2课时)

14.2.1 时间复杂度与空间复杂度-01 - 复杂度的基本概念
- 时间复杂度：算法执行时间与输入规模的关系
- 空间复杂度：算法所需存储空间与输入规模的关系
- 大O记号：渐近上界的表示方法
- 最好、最坏、平均情况分析
14.2.2 时间复杂度与空间复杂度-02 - 复杂度分析方法
- 基本操作的识别
- 循环结构的复杂度分析
- 递归算法的复杂度分析
- 常见复杂度等级：O(1), O(log n), O(n), O(n log n), O(n²)

14.3 算法策略 (12课时)

14.3.1 算法策略知识点概述

算法设计方法 - 不同策略的特点和适用场景
策略选择 - 根据问题特点选择合适的算法策略
效率比较 - 不同策略的时间和空间效率

14.3.2 算法策略概述

分治法 - 分而治之的思想
贪心法 - 局部最优选择
动态规划 - 最优子结构和重叠子问题
回溯法 - 试探性搜索
分支限界 - 广度优先的搜索策略

14.3.3 分治法

基本思想 - 将大问题分解为小问题
设计步骤
1. 分解：将问题分解为若干子问题
2. 解决：递归求解子问题
3. 合并：将子问题的解合并为原问题的解
经典应用
- 归并排序：O(n log n)时间复杂度
- 快速排序：平均O(n log n)时间复杂度
- 二分查找：O(log n)时间复杂度
- 大整数乘法：Karatsuba算法

14.3.4 贪心法

基本思想 - 每步选择当前最优解
适用条件
- 贪心选择性质：局部最优导致全局最优
- 最优子结构：问题的最优解包含子问题的最优解
经典应用
- 活动选择问题
- 分数背包问题
- 哈夫曼编码
- 最小生成树（Prim、Kruskal算法）

14.3.5 动态规划法

基本思想 - 将复杂问题分解为重叠子问题
适用条件
- 最优子结构：最优解包含子问题的最优解
- 重叠子问题：子问题会被多次求解
设计步骤
1. 确定状态：定义dp数组的含义
2. 状态转移：找出状态间的递推关系
3. 初始化：确定边界条件
4. 计算顺序：确定计算的顺序
经典应用
- 0-1背包问题
- 最长公共子序列
- 最长递增子序列
- 编辑距离

14.3.6 回溯法

基本思想 - 试探性地搜索解空间

算法框架

backtrack(当前状态) {
    if (满足结束条件) {
        记录解
        return
    }
    for (每个可能的选择) {
        做选择
        backtrack(新状态)
        撤销选择
    }
}

经典应用
- N皇后问题
- 图的着色问题
- 旅行商问题
- 子集生成

14.4 查找算法 (8课时)

14.4.1 查找算法知识点概述

查找的定义 - 在数据集合中寻找特定元素
查找算法分类 - 静态查找和动态查找
性能指标 - 平均查找长度（ASL）

14.4.2 顺序查找

算法原理 - 逐个比较直到找到目标
时间复杂度 - O(n)
适用场景 - 无序表、小规模数据
改进方法 - 设置哨兵、概率查找

14.4.3 二分查找

算法原理 - 在有序表中折半查找
时间复杂度 - O(log n)

实现要点

cpp

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

变形问题 - 查找第一个/最后一个满足条件的元素

14.4.4 哈希散列表

基本概念 - 通过哈希函数直接访问数据
哈希函数设计
- 除法散列：h(k) = k mod m
- 乘法散列：h(k) = ⌊m(kA mod 1)⌋
- 全域散列：随机选择哈希函数
冲突处理
- 链接法：用链表存储冲突元素
- 开放寻址：线性探测、二次探测、双重散列
性能分析 - 平均情况O(1)，最坏情况O(n)

14.5 排序算法 (10课时)

14.5.1 排序算法知识点概述

排序的定义 - 将数据按某种顺序重新排列
排序算法分类 - 内部排序和外部排序
性能指标 - 时间复杂度、空间复杂度、稳定性

14.5.2 排序的基本概念

稳定性 - 相等元素的相对位置是否改变
内部排序 - 所有数据都在内存中
外部排序 - 数据量大，需要外存辅助
比较排序 - 基于元素间比较的排序

14.5.3 插入类排序

直接插入排序
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 稳定性：稳定
希尔排序
- 时间复杂度：O(n^1.3)
- 空间复杂度：O(1)
- 稳定性：不稳定

14.5.4 选择类排序

简单选择排序
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 稳定性：不稳定
堆排序
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
- 稳定性：不稳定

14.5.6 归并排序

算法原理 - 分治思想，合并有序序列
时间复杂度 - O(n log n)
空间复杂度 - O(n)
稳定性 - 稳定

实现要点

cpp

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

14.5.7 基数排序

算法原理 - 按位数进行多次分配和收集
时间复杂度 - O(d(n + r))，d为位数，r为基数
空间复杂度 - O(n + r)
稳定性 - 稳定
适用场景 - 整数排序、字符串排序

14.5.8 排序算法对比

算法	最好时间	平均时间	最坏时间	空间复杂度	稳定性
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定

14.6-14.7 章节总结 (2课时)

14.6 章节概述 - 知识点梳理和重点回顾
14.7 章节回顾 - 典型题目分析和解题技巧

⏰ 学习时间安排

总学习时间：36课时
建议学习周期：4-5周
每日学习时间：1-2课时
重点难点：算法复杂度分析、动态规划、排序算法

🔍 重点难点

重点内容

复杂度分析 - 熟练分析算法的时间和空间复杂度
算法策略 - 掌握分治、贪心、动态规划的应用
查找算法 - 理解二分查找和哈希表的原理
排序算法 - 掌握各种排序算法的特点和应用
算法设计 - 能够设计简单的算法解决问题

难点突破

递归复杂度 - 使用主定理分析递归算法复杂度
动态规划 - 理解状态转移方程的建立
哈希冲突 - 掌握冲突处理的各种方法
算法优化 - 了解算法改进的常用技巧

📝 考试要点

选择题考点

算法复杂度 (4-5分)
算法策略 (3-4分)
查找算法 (3-4分)
排序算法 (4-5分)

应用题考点

复杂度分析 (5-8分)
算法设计 (8-12分)
算法改进 (5-8分)

预计完成时间：36课时 | 难度等级：★★★★★

🎯 本章课程总览

课程	内容	时长
14.1 算法的特性	建立算法基础认知，掌握算法五大特性、常见描述方式及考试中的判断题思路。	45分钟
14.2 时间复杂度与空间复杂度 (2课时)	建立复杂度分析整体框架，掌握大O思想、常见量级比较与复杂度题作答方法。	45分钟
14.2.1 时间复杂度与空间复杂度-01	聚焦 O(1)、O(n)、O(n²)、O(n³) 的判定逻辑，建立循环类题目快速估算能力。	45分钟
14.2.2 时间复杂度与空间复杂度-02	重点突破 O(logn)、O(nlogn)、O(2ⁿ)、O(n!) 的理解与应用，提升量级比较题得分率。	45分钟
14.3.1 算法策略知识点概述	从命题视角建立算法策略知识框架，理解四大策略适用条件与常见复杂度特征。	45分钟
14.3.2 算法策略概述	掌握从题目特征到策略选择的判断流程，建立策略与经典算法的映射关系。	45分钟
14.3.3 分治法	掌握分治法核心流程、适用条件与复杂度分析方法，能识别二分、归并、快速排序中的分治思想。	45分钟
14.3.4 贪心法	理解贪心法“局部最优”思想与可用边界，掌握活动安排、最优装载等典型题型解法。	45分钟
14.3.5 动态规划法	掌握动态规划核心思想与建模步骤，能完成状态定义、转移方程推导及复杂度分析。	45分钟
14.3.6 回溯法	掌握回溯法深度优先搜索机制、状态树建模与剪枝技巧，提升组合搜索题作答质量。	45分钟
14.4.1 查找算法知识点概述	建立查找算法总框架，掌握顺序查找、二分查找、哈希查找的适用条件与性能比较。	45分钟
14.4.2 顺序查找	掌握顺序查找的执行过程、成功/失败查找长度计算以及哨兵优化思想。	45分钟
14.4.3 二分查找	掌握二分查找适用前提、循环不变量与边界更新规则，避免高频代码填空错误。	45分钟
14.4.4 哈希散列表	掌握哈希查找原理、冲突处理方法与装填因子影响，建立哈希题的稳定解题框架。	45分钟
14.5.1 排序算法知识点概述	建立排序算法整体认知，掌握复杂度、稳定性、空间开销和适用场景四维比较方法。	45分钟
14.5.2 排序的基本概念	系统梳理排序基础术语与判断标准，夯实后续各类排序算法的比较基础。	45分钟
14.5.3 插入类排序	掌握插入类排序思想、复杂度与适用场景，重点区分直接插入排序与希尔排序。	45分钟
14.5.4 选择类排序	掌握选择类排序的工作机制，重点比较简单选择排序与堆排序在复杂度和稳定性上的差异。	45分钟
14.5.6 归并排序	掌握归并排序“分解+归并”流程、复杂度推导与稳定性判断，提升上午题与下午题综合得分能力。	45分钟
14.5.7 基数排序	掌握基数排序按位分配与收集流程，理解其复杂度特征及与比较排序的本质差异。	45分钟
14.5.8 排序算法对比	通过统一对比框架掌握主流排序算法差异，形成考试与实践可复用的选型决策能力。	45分钟
14.6 算法基础章节概述	对第14章进行体系化梳理，打通知识结构与命题逻辑，形成可执行的复习路线图。	45分钟
14.7 算法基础章节回顾	对第14章进行考点复盘、错因归类与冲刺训练设计，帮助建立稳定得分能力。	45分钟

🧭 本章定位（命题老师视角）

本章以“概念辨析 + 计算/推理”混合题为主，强调关键词与方法匹配。
命题常把相近概念放在同题干干扰，需要先判边界再下结论。

🧱 命题主线

主线1：核心概念定义、边界与场景映射。
主线2：典型机制/流程的步骤化理解与应用。
主线3：高频易错点识别与反向排除。

⏱️ 复习优先级（时间不足时）

先做本章高频计算题与判定题。
再做章节概述与回顾中的综合题。
最后复盘错题并补齐概念盲区。

📝 一页速记

模块	快速记忆
核心概念	先记定义，再记边界，再记反例
常用方法	先识别题型，再调用方法模板
易错点	关注关键词、单位、约束条件
作答步骤	条件提取 -> 过程推导 -> 结果校验

⚠️ 高频坑位

概念名词相近但边界不同，容易“看着像就选”。
计算题忘记统一单位、位宽或默认条件。
过程题跳步骤，导致中间量错而全题失分。

🧪 作答模板（客观题/综合题）

第一步：识别题型（概念、流程、计算、综合）。
第二步：提取关键词（对象、条件、约束、目标）。
第三步：调用方法并写出关键中间步骤。
第四步：检查边界（符号、范围、单位、合理性）。

🛣️ 学习路线建议

第一轮：按课程顺序建立知识骨架。
第二轮：按题型专题训练并沉淀模板。
第三轮：只看错题与速记表做考前冲刺。

第14章 算法基础 ​

📚 本章课程 ​

📚 章节概述 ​

🎯 学习目标 ​

📖 课程安排 ​

14.1-14.2 算法基础概念 (4课时) ​

14.1 算法的特性 ​

14.2 时间复杂度与空间复杂度 (2课时) ​

14.3 算法策略 (12课时) ​

14.3.1 算法策略知识点概述 ​

14.3.2 算法策略概述 ​

14.3.3 分治法 ​

14.3.4 贪心法 ​

14.3.5 动态规划法 ​

14.3.6 回溯法 ​

14.4 查找算法 (8课时) ​

14.4.1 查找算法知识点概述 ​

14.4.2 顺序查找 ​

14.4.3 二分查找 ​

14.4.4 哈希散列表 ​

14.5 排序算法 (10课时) ​

14.5.1 排序算法知识点概述 ​

14.5.2 排序的基本概念 ​

14.5.3 插入类排序 ​

14.5.4 选择类排序 ​

14.5.6 归并排序 ​

14.5.7 基数排序 ​

14.5.8 排序算法对比 ​

14.6-14.7 章节总结 (2课时) ​

⏰ 学习时间安排 ​

🔍 重点难点 ​

重点内容 ​

难点突破 ​

📝 考试要点 ​

选择题考点 ​

应用题考点 ​

🎯 本章课程总览 ​

🧭 本章定位（命题老师视角） ​

🧱 命题主线 ​

⏱️ 复习优先级（时间不足时） ​

📝 一页速记 ​

⚠️ 高频坑位 ​

🧪 作答模板（客观题/综合题） ​

🛣️ 学习路线建议 ​

第14章算法基础

📚 本章课程

📚 章节概述

🎯 学习目标

📖 课程安排

14.1-14.2 算法基础概念 (4课时)

14.1 算法的特性

14.2 时间复杂度与空间复杂度 (2课时)

14.3 算法策略 (12课时)

14.3.1 算法策略知识点概述

14.3.2 算法策略概述

14.3.3 分治法

14.3.4 贪心法

14.3.5 动态规划法

14.3.6 回溯法

14.4 查找算法 (8课时)

14.4.1 查找算法知识点概述

14.4.2 顺序查找

14.4.3 二分查找

14.4.4 哈希散列表

14.5 排序算法 (10课时)

14.5.1 排序算法知识点概述

14.5.2 排序的基本概念

14.5.3 插入类排序

14.5.4 选择类排序

14.5.6 归并排序

14.5.7 基数排序

14.5.8 排序算法对比

14.6-14.7 章节总结 (2课时)

⏰ 学习时间安排

🔍 重点难点

重点内容

难点突破

📝 考试要点

选择题考点

应用题考点

🎯 本章课程总览

🧭 本章定位（命题老师视角）

🧱 命题主线

⏱️ 复习优先级（时间不足时）

📝 一页速记

⚠️ 高频坑位

🧪 作答模板（客观题/综合题）

🛣️ 学习路线建议