复习
复习
第一章导引 掌握: 1算法的定义及其性质(1.1节) 2算法分析的基础知识(12节) 重要的约定和假设 关于O,Ω,Q的定义 了解: 3 SPARKS语言(13节) 4常用数据结构(14节) 5.递归与消去递归(1.5节)
第一章 导引 掌握： 1.算法的定义及其性质(1.1节) 2.算法分析的基础知识(1.2节) • 重要的约定和假设 • 关于O，Ω， 的定义 了解： 3.SPARKS语言(1.3节) 4.常用数据结构(1.4节) 5.递归与消去递归(1.5节)
第二章分治法 掌握: 基本知识 分治法的基本思想:2.1节 关系式的化简: 1)递推关系式的化简作业题 2)常用求和公式 在统计语句的频率时,求和公式的一般形式为: ∑∫() g(n)≤i≤h(n) 特殊形式∑=(m)∑=m+1)12=m l≤i<n ∑2=n(n+1)2n+1)6=(n) 1≤i≤n
第二章 分治法 掌握： 1.基本知识 分治法的基本思想：2.1节 关系式的化简： 1）递推关系式的化简 作业题 2）常用求和公式 在统计语句的频率时，求和公式的一般形式为： ( )ih(n) ( ) g n f i n( 1)/ 2 ( ) 2 1 i n n i n = + = 特殊形式 ( ) 1 1 + = k i n k i n n( 1)(2 1)/ 6 ( ) 3 1 2 i n n n i n = + + =
第二章分治法(续) 2重要实例 二分检索算法及其算法分析:2.2节 基于 PARTITION的选择算法:2.6节 3分类算法及其应用:24、2.5节 般了解: 4找最大和最小元素:23节 5.最坏情况时间是(n)的选择算法:23节后半部分
第二章 分治法（续） 2.重要实例 • 二分检索算法及其算法分析：2.2节 • 基于PARTITION的选择算法：2.6节 3.分类算法及其应用：2.4、2.5节 一般了解： 4.找最大和最小元素：2.3节 5.最坏情况时间是O(n)的选择算法：2.3节后半部分
第三章贪心方法 掌握: 1.基本知识(3.1节) 基本概念:约束条件、目标函数、可行解、 最优解 贪心方法的适用对象:求输入的一个可行的 子集 贪心方法的一般策略:度量标准 贪心解是问题最优解证明的基本思想
第三章 贪心方法 掌握： 1.基本知识（3.1节） • 基本概念：约束条件、目标函数、可行解、 最优解 • 贪心方法的适用对象：求输入的一个可行的 子集 • 贪心方法的一般策略：度量标准 • 贪心解是问题最优解证明的基本思想