一、时间复杂度：InsertionSort的运行时间是Ω(n)排序问题的比较次数为Ω(nlog n)SelectionSort算法和BottomUpSort算法可分别使用Θ(n2)和Θ(nlog2n)描述任何基于比较的排序算法，可以证明它的运行时间必定是Ω(nlog n)◆通常把时间复杂性为O(nlog n)的基于比较的排序算法，称为该问题的最优算法。

◆根据这一定义，算法BottomUpSort是该问题的最优算法二、空间复杂度算法LinearSearch空间复杂性为Θ(1)算法Merge空间复杂性为Θ(n)三、基本的符号（O类似于≤、Ω类似于≥、Θ类似于= 、o类似于<）O符号提供了一个运行时间的上界Ω符号在运行时间的一个常数因子内提供一个下界。

Θ符号给出算法运行时间增长率的一个精确描述。

Ω符号定义的一个重要推论：f(n)= Ω(g(n))，当且仅当g(n)=O(f(n))Θ符号定义的一个重要推论：f(n)= Θ(g(n))当且仅当f(n)=O(g(n))并且g(n)=O(f(n))任一常数函数是O(1)、Ω(1)、Θ(1)一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设v是一个结点，p(v)是v的父结点，那么存储在p(v)中的数据项键值大于或等于存储在v中的数据项键值。

堆的蕴含特性：沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。

◆T的根结点存储在H[1]中；◆设T的结点存储在H[j]中，如果它有左子结点，则这个左子结点存储在H[2j]中；如果它还有右子结点，这个右子结点存储在H[2j+1]；◆若元素H[j]不是根结点，它的父结点存储在H[⎣j/2⎦]中。

由“几乎完全二叉树” 的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。

堆具有如下性质：key(H[⎣j/2⎦])≥key(H[j]) 2≤j≤n创建堆①方法一给出有n个元素的数组A[1..n]，要创建一个包含这些元素的堆可以这样进行：首先假设堆由1个元素构成，然后将第2个、第3个元素插入堆，直至n个。

②方法二设数组A有n=10个元素，构造它的几乎完全二叉树T。

构造一个n元素的堆，算法MakeHeap需要Θ(n)时间和Θ(1)空间算法HeapSort对n个元素排序，需要用O(nlog2n)时间和Θ(1)空间最大堆：最大键值元素存放在根结点。

最小堆：最小键值元素存放在根结点由于堆树的高度为⎣log2n⎦，所以删除一个元素所需的时间为O(log2n)。

堆排序不稳定。

用根树来表示每个集合，集合中的元素存储在节点中，树中除根节点外的每个元素X都有一个指向父节点P（X）的指针。

根有一个空指针，用做集合的名字或集合的代表。

这样产生了森林，其中每一棵树对应于一个集合。

㈡不相交集数据结构①将用于命名子集的元素视为根，其余元素视为其后代，每个子集可用一棵根树来表示，这样便形成了森林。

②除根结点外，每个结点都有一个指针指向父结点。

根结点用作集合的名字。

根结点的指针值为0，表示不指向任何结点。

③森林可方便地用数组A[1..n]，A[j]是j的父结点，A[j]=0表示j是根结点。

④对于任一元素x，用root(x)表示包含x的树的根，例root(6)=3。

归纳法也叫尾递归，指算法一般只调用一次递归。

基数排序法时间复杂性Θ(n)空间复杂性◆若采用数组，除需大小为n*10的二维数组外，还需记录表Li中的元素个数的数组Len[0..9]，故算法需10n+10个存储单元，空间复杂性可用Θ(n)表示。

◆若采用链表，仅需准备10个空表，无需额外的存储空间，故算法空间复杂性为Θ(1)。

说明：基于比较的排序算法的时间复杂性为Ω(nlog2n)，而基数排序法的时间复杂性为Θ(n)，基数排序法不是采用比较方法来实现的。

1. for j←1 to k2. 准备10个空链表L0,L1,...,L93. while L非空4. a←L中的第一个元素:从L删除该元素5. i←a中第j位数字: 将a加入Li6. end while7. L←L08. for i←1 to 99. L←L,Li //将表Li添加到表L的尾部10. end for11. end for12. return L四、整数幂整数幂的递归和非递归算法，这种方法仅需Θ(log2n)次乘法。

（二）递归算法算法5.4 ExpRec(Page 93-94)输入：实数x和非负整数n输出：xn1. PowerRec(2,5)过程0. procedure PowerRec(x,n)1. if n=0 then y←12. else3. y←PowerRec(x, ⎣n/2⎦ )4. y←y*y5. if n是奇数then y←xy6. end if7. return y8. end procedure㈢非递归算法A算法5.5_1 Exp (Page 94)输入：实数x和非负整数n输出：xn1. PowerA(2,10) //PowerA(2,1010)过程0. procedure PowerA(x,n)1. y←12. 将n用二进制数dkdk-1...d1 表示3. for j←k downto 14. y←y*y5. if dj=1 then y←xy6. end for7. return y8. end procedure五、多项式求值（Horner规则）算法5.6 Hormer(Page 95)输入：a n , a n-1 ,..., a0和x输出：Pn(x) = a n x n+a n-1x n-1+...+a2x2+a1x+a01. p←an2. for j←1 to n3. p←xp+a n-j4. end for5. return p六、生成排列运行时间算法5.7 Permutations1（Page95-96）输入：正整数n输出：数1,2, …,n的所有可能排列1. for j←1 to n //置初值2. P[j]←j3. end for4. perm1(1) //调用过程过程perm1(m)0. procedure perm1(m)1. if m=n then output P[1..n]2. else3. for j←m to n4. 互换P[j]和P[m] //在调用前交换5. perm1(m+1) //调用过程（n-m个数在P[m+1..n]中）6. 互换P[j]和P[m] //在调用后恢复原状态7. end for8. end if9. end procedure七、寻找多数元素2>寻找候选者算法Candidate(int A[],int m ,int n){//寻找A[m...n]中多数元素候选者j=m;c=A[m];count=1;for(j=m+1;j<n&&count>0){if(A[j]==c)count++else count--;}if(j==n)return c;else return canditate(j+1); //对A[j+1...n]寻找多数元素候选者。

}3>判断数组有无多数元素算法Majority(int A[],int n){c=conditate(1);count=0;for(i=1;i<=n;i++)if(A[j]==c)count++if(count>n/2)return c;else return 0; //设数组A中元素均非0，返回0表示不存在多数元素，}八、分治范式在n个元素组成的数组中，算法BinarySearchRec搜索某个元素递归执行过程的次数不超过⎣log2n⎦ +1。

算法的时间复杂性为O(log2n)。

BinarySearchRec（递归）的空间复杂性为O(log2n)，而二分搜索法的迭代算法仅需Θ(1)空间算法MergeSort对一个n个元素的数组排序所需的时间是Θ(nlog2n)，空间是Θ(n)。

分治范式有以下步骤组成：1、划分步骤；2、治理步骤；3、组合步骤。

一个分治算法有如下形式：◆如果实例I 的规模小到可用简单方法求解，则直接返回答案，否则继续下一步。

◆把实例I 分割成p 个大小几乎相同的子实例I1、I2、...、Ip。

◆对每个子实例Ij (1≤j≤p)递归调用算法，并得到p个部分解。

◆组合p 个部分解的结果，便可得到原实例I 的解，并返回实例的解。

九、寻找中项和第K小元素十、快速排序划分算法：算法6.5(参见Page 113)输入：数组A[1..n]和下标low、high输出：划分元素A[low]在子数组A[low..high]中的适当位置w，即y∈A[low..w-1]≤A[w]＜y∈A[w+1..high]过程0. procedure Split(A[1..n],low,high)1. i←low //初始时i指向A[low]2. x←A[low] //处理过程中有：A[low..i]≤x=A[low]3. for j←low+1 to high //j指向当前处理的元素4. if A[j]≤x then //处理过程中有：A[i+1..j]>x=A[low]5. i←i+16. if i≠j then 互换A[i]和A[j]7. end if8. end for9. if low≠i then 互换A[low]和A[i]10. w←i11. return w12. end procedure快速排序：在最坏情况下，算法QuickSort的运行时间是Θ(n2)。

然而，若主元始终是中项元素，它的时间复杂性为Θ(nlog2n)。

算法QuickSort对n个元素进行排序，所执行的平均比较次数为Θ(nlog2n)算法6.6 QuickSort（参见Page 114）输入：有n个元素的数组A[1..n]输出：按升序排列的数组A[1..n]1. QuickSort(A,1,n)过程0. procedure QuickSort(A[1..n],low,high)1. if low<high then2. w←Split(A,low,high) //A[w]元素在恰当位置3. QuickSort(A,low,w-1)4. QuickSort(A,w+1,high)5. ens if6. end procedure十一、矩阵乘法6.X 循环赛日程表（分治法应用）十二、最近点对问题(知道)十三、动态规划：①最长公共子序列问题递归算法的时间复杂性为O(2m+n)。

最长公共子序列问题的最优解可在Θ(nm)时间和Θ(min｛m,n｝)空间内得到。

②矩阵链相乘所有点对的最近点对问题算法的时间复杂性为Θ(n3)，空间复杂性为Θ(n2)③背包问题背包问题的最优解可在Θ(nC)时间内和Θ(C)空间内得到二十、贪心算法：④活动安排问题当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动；如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。