第一、二章 基本概念

纲要

• 循环不变式
• 伪代码范式
• 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

Q&A

• 算法的基本概念和性质
• 算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算
• 什么是循环不变式？用循环不变关系证明循环的正确性
  • 在第一次进入循环之前成立、以后每次循环之后还成立的关系
  • 分三步走： 1）初始化：证明初始状态时循环不变式成立，即证明循环不变式在循环开始之前为真； 2）保持：证明每次循环之后、下一次循环开始之前循环不变式仍为真； 3）终止：证明循环可以在有限次循环之后终止，终止时循环不变式依然为真

第三章

纲要

• 上界、下界、渐进紧确界：Ω、O、Θ
• 非渐进紧确界：w、o
• 限界函数性质：传递性、自反性、对称性、转置对称性
• 相关定理（用于估算限界函数）：多项式定理、阶大小定理
• 指数时间算法、多项式时间算法
• n 较大时，大于nlogn的算法比较困难

Q&A

第四章 分治策略

纲要