算法设计与分析

课程讲义

• 2026年秋第4次课：从汉诺塔与快速幂衔接到合并排序、逆序对，再比较二分答案和枚举递推的依据。
• 2026年秋第5次课：串联快速排序、木材加工与最长公共前缀，比较按基准划分、利用单调性排除候选和合并子问题摘要。
• 2026年秋第6次课：以打家劫舍、矩阵连乘和最大子数组和讲解动态规划，比较前缀状态、区间状态与必须结尾的状态。

分治法专题

递归与分治专题导学串联学习路线，比较子问题、返回值和合并成本。

• 同时求数组的最大值与最小值（简单）：学习两个极值的返回与合并，以及元素比较次数的分析。
• 最长公共前缀（简单）：分组求前缀，逐字符合并，并分析中间字符串的空间。
• 有序数组构造平衡二叉搜索树（简单）：按中点构造子树，区分递归栈与输出树的存储。
• 合并k个有序数组（中等）：均衡安排合并顺序，区分数组个数与元素总数。
• 二维有序矩阵查找（中等）：依据行列单调性排除区域，递归查找两块剩余候选。
• 四叉树构建与二值图像压缩（中等）：用前缀和判断一致区域，四分构造可恢复图像的树。
• 重要逆序对（中高难度）：在归并前统计加倍条件，比较普通逆序对与负数边界。
• Karatsuba大整数乘法（高难度）：以三次半长乘法代替四次，按整数位数分析成本。
• 平面最近点对（高难度）：处理跨分界线点对，用几何约束限制条带中的候选数量。
• Strassen矩阵乘法（高难度）：用七次子矩阵乘法重组结果，分析补零及渐近优势的适用范围。

递归学习实例

• 猴子吃桃：根据最后一天的数量反推，学习递归调用、返回和循环实现。
• 二分法求幂（快速幂）：将指数减半，复用子问题结果，学习对数级递归和循环实现。
• 合并排序：通过递归拆分数组并合并有序子数组，学习分治算法、稳定性与复杂度分析。
• 快速排序：先按基准划分，再分别排序两侧，学习区域不变式、原地交换与最坏情况分析。
• 逆序对：在合并排序中批量统计跨段配对，理解三类计数、重复值处理及排序与计数的关系。
• 约瑟夫环：理解报数出局、编号转换，比较递归公式、循环公式和列表模拟。
• 汉诺塔：学习两次递归调用、柱子角色交换，以及完整移动和指定步骤查询。

二分答案学习实例

• 木材加工：利用可切段数的单调性，寻找最大的可行木段长度，掌握闭区间二分与边界处理。

枚举与递推学习实例

• 费解的开关：枚举第一行状态，再逐行确定后续操作，学习状态转移与最少操作次数的枚举求解。

动态规划学习实例

• 打家劫舍：从选与不选推导前缀最优值，对照状态表与滚动变量，区分直线模型和环形扩展。
• 矩阵连乘：枚举最后一次相乘的切分点，按区间长度填表并恢复一种最优括号方案。
• 最大子数组和：定义必须结尾的状态，比较状态表、滚动变量与四项摘要分治，核对连续性和全负数边界。

1. 为什么要上算法这门课？（这门课能为你带来什么？）

• 基础技能：算法是计算机科学的基础之一。掌握算法设计和分析可以帮助学生理解计算机程序和系统是如何工作的。

• 解决问题：算法可以帮助解决各种复杂问题，学习算法设计可以提高解决问题的能力。

• 编程能力：通过学习算法，学生可以提高编程技巧，编写更高效、更优化的代码。

• 逻辑思维：算法设计需要严密的逻辑推理，这有助于培养清晰的思维和分析能力。

• 职业发展：许多技术职位，特别是在软件开发、数据分析和人工智能领域，都要求具备算法知识。

• 研究潜力：算法设计与分析是进行计算机科学研究的基础，对于有志于学术研究的学生来说非常重要。

• 创新能力：了解和掌握算法可以帮助学生开发新的技术解决方案，推动科技创新。

2. 如何学习好好算法这门课

• 建立坚实的基础 数据结构：熟悉各种数据结构（如数组、链表、栈、队列、树、图等），了解它们的特点和适用场景。 数学基础：掌握必要的数学知识，如离散数学、概率论和统计学，这些知识对于理解和证明算法的正确性和效率至关重要。 编程语言：熟练掌握至少一种编程语言，如Python、Java、C++等，并能够在该语言中实现算法。
• 学习核心概念 算法分类：了解不同类型的算法，如贪心算法、动态规划、分治策略、回溯算法等。 时间复杂度与空间复杂度：学习如何分析算法的时间复杂度和空间复杂度，以便评估算法的效率。 递归与迭代：掌握递归和迭代的概念及其在算法设计中的应用。
• 实践练习 做题：通过在线平台（如LeetCode、Codeforces、HackerRank等）练习算法题，提高解题能力。 项目实践：参与实际项目，将所学知识应用于解决具体问题。 参加竞赛：参加ACM ICPC等编程竞赛，锻炼自己的实战能力。
• 阅读经典教材 《算法导论》（Introduction to Algorithms，作者：Thomas H. Cormen 等）：这是一本经典的算法教科书，适合初学者和进阶学习者。 《算法（第四版）》（Algorithms, Fourth Edition，作者：Robert Sedgewick 和 Kevin Wayne）：提供了丰富的实例和实践指南。 《算法设计手册》（The Algorithm Design Manual，作者：Steven S. Skiena）：涵盖了大量实用的算法技巧和实例。

3. 本课程的讲授方法（这门课怎么上）

• 教学理念 以实践为主：通过实际的编程练习，让学生亲自动手解决问题，从而更好地理解算法的设计思想和实现细节。 案例驱动：采用LeetCode或蓝桥杯等平台上的经典题目作为教学案例，通过解决这些问题来引导学生学习和总结算法知识。 归纳总结：在解决具体问题的基础上，引导学生归纳总结出通用的算法设计模式和分析方法。
• 主要教学内容 分治法 动态规划 贪心算法 回溯法 分支限界法 等

4. 考核方式

• 平时成绩
• 实践成绩（课后作业和课程实验）
• 期中成绩
• 期末成绩

5. 学习纪律

• 签到次数不能少于总数的三分之二
• 实践作业次数不能少于总数的三分之二
• 上课认真听讲，积极讨论