第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 分治法
- 基本思想 - 将大问题分解为小问题
- 设计步骤
- 分解：将问题分解为若干子问题
- 解决：递归求解子问题
- 合并：将子问题的解合并为原问题的解
- 经典应用
- 归并排序：O(n log n)时间复杂度
- 快速排序：平均O(n log n)时间复杂度
- 二分查找：O(log n)时间复杂度
- 大整数乘法：Karatsuba算法
14.3.4 贪心法
- 基本思想 - 每步选择当前最优解
- 适用条件
- 贪心选择性质：局部最优导致全局最优
- 最优子结构：问题的最优解包含子问题的最优解
- 经典应用
- 活动选择问题
- 分数背包问题
- 哈夫曼编码
- 最小生成树（Prim、Kruskal算法）
14.3.5 动态规划法
- 基本思想 - 将复杂问题分解为重叠子问题
- 适用条件
- 最优子结构：最优解包含子问题的最优解
- 重叠子问题：子问题会被多次求解
- 设计步骤
- 确定状态：定义dp数组的含义
- 状态转移：找出状态间的递推关系
- 初始化：确定边界条件
- 计算顺序：确定计算的顺序
- 经典应用
- 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(n1.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课时 | 难度等级：★★★★★