InsertionSort的运行时间是Ω(n) 排序问题的比较次数为Ω(nlog n)
2
SelectionSort算法和BottomUpSort算法可分别使用Θ(n)和Θ(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 k
2. 准备10个空链表L0,L1,...,L9
3. while L非空 4. a←L中的第一个元素 :从L删除该元素 5.
i←a中第j位数字 : 将a加入Li
6. end while 7. L←L0
8. for i←1 to 9 9.
L←L,Li //将表Li添加到表L的尾部
10. end for
11. end for 12. return L
四、整数幂 整数幂的递归和非递归算法，这种方法仅需Θ(log2n)次乘法。 （二）递归算法
算法5.4 ExpRec(Page 93-94) 输入：实数x和非负整数n 输出：xn
1. PowerRec(2,5) 过程
0. procedure PowerRec(x,n) 1. if n=0 then y←1 2. else 3. y←PowerRec(x, n/2 ) 4. y←y*y 5.
if n是奇数 then y←xy
6. end if 7. return y
8. end procedure ㈢非递归算法A
算法5.5_1 Exp (Page 94) 输入：实数x和非负整数n 输出：xn
1. PowerA(2,10) //PowerA(2,1010) 过程
0. procedure PowerA(x,n) 1. y←1
2. 将n用二进制数dkdk-1...d1 表示 3. for j←k downto 1 4.
y←y*y
5. if dj=1 then y←xy 6. end for
7. return y
8. end procedure
五、多项式求值（Horner规则） 算法5.6 Hormer(Page 95) 输入：an , an-1 ,..., a0和x
输出： Pn(x) = anx+an-1x+...+a2x+a1x+a0 1. p←an
2. for j←1 to n 3. p←xp+an-j
n
n-1
2
4. end for 5. return p
六、生成排列运行时间
算法5.7 Permutations1（Page95-96） 输入：正整数n
输出：数1,2, …,n的所有可能排列 1. for j←1 to n //置初值
2. P[j]←j
//调用过程
3. end for 4. perm1(1) 过程 perm1(m)
0. procedure perm1(m)
1. if m=n then output P[1..n]
2. else
3. for j←m to n
4. 互换P[j]和P[m] //在调用前交换
5. perm1(m+1) //调用过程（n-m个数在P[m+1..n]中） 6. 互换P[j]和P[m] //在调用后恢复原状态 7. end for 8. end if 9. 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 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. 3. 4. 5. x←A[low] //处理过程中有：A[low..i]≤x=A[low] for j←low+1 to high //j指向当前处理的元素 if A[j]≤x then //处理过程中有：A[i+1..j]>x=A[low] i←i+1 if i≠j then 互换A[i]和A[j] end if 6. 7. 8. end for 9. if low≠i then 互换A[low]和A[i] 10. w←i 11. return w 12. 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 6.X 循环赛日程表（分治法应用） 十二、 最近点对问题(知道)十三、 动态规划： ①最长公共子序列问题 递归算法的时间复杂性为O(2m+n)。最长公共子序列问 题的最优解可在Θ(nm)时间和Θ(min｛m,n｝)空间内得到。 ②矩阵链相乘 所有点对的最近点对问题算法的时间复杂性为Θ(n3)，空间复杂性为Θ(n2) ③背包问题 背包问题的最优解可在Θ(nC)时间内和Θ(C)空间内得到 二十、贪心算法： ④活动安排问题 当输入的活动已按结束时间的非减序排列，算法只需O(n)的时 间安排n个活动 ；如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。 public static int greedySelector(int s[],int f[], boolean a[]) { int n=s.length-1; a[1]=true; int j=1; int count=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; } return count; } ⑤最优装载问题（最优解） 最短路径问题 给出一个具有非负权有向图G和源结点s，算法Dijkstra在时间O(n)内找出从s到其 它各结点的最短路径 最小耗费生成树（Kruskal算法 稀疏图）在一个含有m条边的含权连通无向图中，算法Kruskal可在O(mlog2m)时间内找出最小耗费生成树 最小耗费生成树（Prim算法 稠密图）算法Prim在一个有n个顶点的含权无向图中找出最小耗费生成树要用时间O(n2) 二十一、贪心算法和动态规划的异同点？ 动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解； 不同点： 贪心算法：①贪心算法中，作出的每步贪心算法决策都是无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留。②贪心算法正确的条件是：每一步的最优解一定包含上一步的最优解。 动态规划：①全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。②动态规划的关键是状态转移方程，即如何由已求出的局部最优解来推导全局最优解。③边界条件：即最简单的，可以直接得出的局部最优解 二十二、讲过的算法哪些属于NP完全问题？ 哈密顿回路问题（旅行商问题）、图3着色问题、多处理机调度问题等等 定义10.3 NP类（P177） 判定问题的NP类由这样的判定问题组成，对于它们存在多项式时间内运行的不确定性算法。 7．P类和NP类的区别（P177） P是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定 或解出。 NP是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内检 查或验证它们的解。 8．NP完全问题 如果一个NP问题的所有可能答案，都可以在多项式时间内进行正确与否验证的话，那么该问题称为“完全多项式非确定性问题”，简称NP完全问题（或NPC问题）。NP完全问题是NP类的一个子类。 二十三、 子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树为子集树（如0/1背包的解空间树）遍历排列树需要O(n!)计算时间 排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树为排列树（如 2 n后问题的解空间树）遍历排列树需要O(n!)计算时间 二十四、 具有限界函数的深度优先生成法称为回溯法 回溯法是通过每次增加一个结点来寻求解。 • 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法 搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树， 继续按深度优先策略搜索。 回溯法的基本思想： (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。 二十六、3着色问题不一定有解，8皇后问题一定有解。 8皇后问题用的是什么树？ 二十七、随机算法比起传统的有什么区别或者优异？ 随机化算法是这样一种算法：在算法中使用了随机函数（这里的随机函数不妨泛指pascal中的random(n)，其返回值为[0,n-1]中的某个整数，且返回每个整数都是等概率的），且随机函数的返回值直接或间接地影响了算法的执行流程或执行结果。 若一个算法是随机化算法，则它执行的流程或结果就会受其使用的随机函数的影响，我们按影响的性质和程度分为下列三种情况： （１）随机不影响执行结果。这时随机必然影响了执行的流程，其效应多表现为算法的时间效率的波动； （２）随机影响执行结果的正确性。在这种情况中，原问题要求我们求出某个可行解；或者原问题为判定性问题，随机效应表现为程序执行后得到正确解的概率； （３）随机影响执行结果的优劣。这时，随机效应表现为实际执行结果与理论上的最优解或期望结果的差异。 由于随机化算法的执行情况受到随机函数这种不确定因素的支配，因此即使同一个算法在多次执行中用同样的输入，其执行情况也会不同，至少略有差异。差异可能表现为出解速度快慢、解正确与否、解的优劣等等。 从以下四个方面分析随机化算法的性能。1.时间效率；2.解的正确性；3.解的优劣程度（解与最优解的接近程度）；4.稳定性，即算法对同样的输入数据执行后输出结果的变化，变化越小则越稳定。非随机化算法的稳定性为100%，随机化算法的稳定性属于区间[0%,100%]。稳定性可以是算法的平均时间复杂度，也可以是执行算法得到正确解的概率，还可以是实际解达到某一优劣程度的概率。稳定性是评判随机化算法好坏的一个重要指标。 以常用的“快速排序算法”为例，它的基本思想是递归，即将待排序的一组数划分为两部分，前一部分的每个数不大于后一部分的每个数，然后继续分别对这两部分作划分，直到待划分的那部分数只含有一个数为止。 快速排序在最坏情况下（每次划分都使p=lo）的时间复杂度为o(n2)，在最优情况下的时间复杂度为o(nlog2n)。如果假设输入中出现各种排列都是等概率的（但实际情况往往不是这样），则算法的平均时间复杂度为o(nlog2n)。通过分析和实践证明，在最坏情况下，而n又 较大时，快速排序的速度就很慢， 用随机化来优化快速排序。随机化快速排序的思想是：每次划分时从a[lo..hi]中随机地选一个数作为x对a[lo..hi]划分，只需对原算法稍作修改就行了， 随机化快速排序的时间效率依然依赖于每次划分选取的数在排好序的数组中的位置，其最坏、平均、最佳时间复杂度依然分别为o(n2)，O(nlog2n) ，O(nlog2n)，只不过最坏、最佳情况不再由输入所决定，而是由随机函数所决定。也就是说，我们无法通过给出一个最坏的输入来使执行时出现最坏情况 执行结果确定的随机化算法原理是：用随机函数全部或部分地抵消最坏输入的作用，使算法的时间效率不完全依赖于输入的好坏，通过对输入的适当控制，使得执行结果相对稳定 因篇幅问题不能全部显示，请点此查看更多更全内容