1、算法设计与分析复习提纲 2011.06.121 引言(ch1)1. 什么是算法及其特征算法是通过一系列有限的指令集构成的对特定问题进行求解的计算机执行描述。算法特征：输入、输出、有限性、确定性、通用性2. 问题实例和问题规模问题实例：解决一个问题所需要的所有输入问题规模：算法输入实例的大小2 算法初步(ch2)1. 插入排序算法INSERT_SORT(A)for j0 and Aikeydo Ai+1n0 时有 c1g(n)=n0 时有 0=n0 的时候有 f(n)=cg(n)成立（注：证明的时候找出符合条件的 n0 和 c 即可）2. 标准复杂性函数及其大小关系(1)多项式时间阶的大小O(1
2、)n0 时候一切都符合猜测的结论)c.有时候得到 T(n)ARandom(1,n);/直接就地生成优先级后就交换位置时间复杂度：(n)3.online 雇佣问题及其概率分析(略)6 堆排序(ch6)1 堆的概念和存储结构堆是一种数据结构它是一种数组对象，可以视为一棵完全二叉树。每一层都是满的，最后一层可能除外。2.堆的性质和种类(1)子节点和父节点下标之间的关系某节点的下标是 i，则 left(i)=2i,right(i)=2i+1Parent(i)=(i/2)的下取整。(2)n 个节点的堆其叶子节点为(n/2)+1,(n/2)+2 n3.堆的操作：建堆；整堆；建堆操作是建立在整堆基础上的，整
3、堆的原理是：假设 i 的以左孩子为根的子树和以右孩子为根的子树均为整好堆的大根堆，需要将 i 节点的值与 left(i)和right(i)节点的值做比较，如果 i 节点值最大则无需整堆已经是大顶堆,如果不是则找出左右孩子的最大值并交换 i 节点和子孩子节点的值，由于交换的过程中可能破坏了该子树的大顶堆的性质，则需要从该子节点开始继续整堆，是个递归的过程。MAX-HEAPIFY(A,i)lAithen largestAlargestthen largestAlargestMAX-HEAPIFY(A,largest)时间复杂度：O(logn)建堆：从 lengthA/2 处开始整堆，直至树根。BU
4、ILD-MAX-HEAPIFY(A)heap-sizeAAiheap-sizeA1 and Ai.parentAheap-sizeA;heap-sizeA-;MAX-HEAPIFY(A,1)/O(logn)/显然时间复杂度为 O(logn)(4)增值HEAP-INCRESE-KEY(A,i,key)/将 Ai增至 keyif(Ai=key)/往下调整then Ai1 and AparentiAj;Ai+1Ar;/Ar就位return i+1;/返回 q快速排序实际上是一个就地（Inplace ）排序。性能分析：（1） 最坏的划分：Ap.q-1,Aq+1,r 有一个是空的T(n)=T(n-1)+
5、T(0)+(n)/ 数组最后一个元素是最大的情况（做为划分源） ，前面是 n-1 个元素，后面元素个数为 0。(n)为生成划分源的时间。由迭代法：T(n)= (n 2)（2） 最好的划分：比较平均，两部分一样大T(n)Ai;/将 Ai交换到最后，因为 partition 是以最后元素作为划分源的Return Parition(A,p,r);/返回划分源 q期望时间为 1.44nlogn(knuth 时间分析)，为 O(nlogn)。8 线性时间排序(ch8)1. 基于比较的排序算法下界：(nlogn)可以用判定树进行说明。2. 计数排序适应的排序对象、算法和时间适应的排序对象：一列有相同元素或
6、没有相同元素的整数数列。元素互不相同时的算法：SpecialCountingSort(A,B)/B1.n为排序结果for i1 to n doBAiAi; /如Ai=5，就放到B5中，小于5的元素不超过5个。时间：O(n) ，无比较，当数组不是连续的整数时比较浪费空间。有相同元素时的算法：CountingSort(A,B,k)/B1.n为排序结果，C1.k为计数数组for i1 to k do Ci0;for j1 to lengthA do /扫描A，值相同元素计数CAj+;for i2 to k do /Ci修改，累计计数CiCi+Ci-1;for jlengthA downto 1 do
7、 BCAjAj;CAj-;时间：T(n,k)=(n+k)=(n) ，如果 k=(n)时3. 基数排序适应的排序对象、算法和时间适应的排序对象：用 k 进制表示为不超过 d 位数的整数序列。算法：RadixSort(A,d) for i1 to d do使用稳定的排序算法对A的第i位排序；/如计数排序时间：T(n)=(d(n+k) /k 为基，d 为位数4. 桶排序适应的排序对象、算法和时间适应的对象：均匀分布在0,1)上的实数列。算法描述：BucketSort(A) nlengthA;for i1 to n do /扫描A，时间为(n)将Ai插入到链表B nAi中;for i0 to n-1
8、do/时间为(n) *用插入排序将Bi排序;将B0, B1, Bn-1连接起来;/时间为(n)*注： n个数是均匀分布在0,1)中， 每个桶中大约只有一个数， 时间为 O(1)9 中位数和顺序统计(ch9)1. 最大和最小值的求解方法方法一：分别独立求，比较次数为(n-1)+(n-2)=2n-3 次方法二：成对输入 x,y 每对比较三次 比较x, y； 将min(x, y)与当前最小值比较； 将max(x, y)与当前最大值比较；总比较次数约为3 n/2 。/第一对元素比较一次，最后一组元素若为一个，至多比较二次2. 期望时间为线性的选择算法利用快排序的随机划分法，进行问题的划分 划分Ap.r
9、 Ap.q-1AqAq+1.r ；/ Aq为划分元 kq-p+1； /即Aq是第k个最小元 if (i=k) then / k = 左区间长度+1return Aq；if (ik) then 在左区间中继续找第i个元素；if (ik) then 在右区间中继续找第i-k个元素；临界条件：当区间长度为 1 时，直接返回该元素RandomizedSelect(A, p, r, i) /选择ith元素if p=r then return Ap;/处理临界条件qRandomizedPartition(A, p, r);/随机产生划分源kq-p+1; /Aq是第k小的元素if i=k thenretur
10、n Aq; /Aq是第i小元素else if ik then /第i小元素落在左区间return RandomizedSelect(A, p, q-1, i);else /第i小元素落在右区间return RandomizedSelect(A, q+1, r, i-k);最好：每次划分为相等的左右区间T(n)=T(n/2)+n T(n)=(n)/由master定理的case3最坏：每次划分为不均等的左右区间T(n)=T(n-1)+n T(n)=(n 2)/由迭代法平均(期望)：分析略。T(n)=(n)/平均时间期望同最好情况3. 最坏时间为线性的选择算法及其时间分析While n1 doste
11、p 1. 将n个元素分成5个1组，共n/5 组。其中最后 1组有n mod 5个元素。/O(1)step 2. 用插入排序对每组排序，取其中值。若最后1组有偶数个元素，取较小的中值。/O(1)step 3. 递归地使用本算法找找n/5 个中值的中值 x。/T(n/5)step 4. 用x作为划分元对A数组进行划分，并设x是第k个/O(n)最小元。step 5. if i=k then return x;/至多T(7n/10+6)else if i140， 有n/(n-70)2 取c20a -cn/10+7c+an0故 T(n)=O(n)10 递归与分治法(sch1)1. 递归设计技术把问题划分
12、为更小规模的和原问题同等问题的子问题，子问题解决了，原问题就解决了2. 递归程序的非递归化用栈消除递归利用迭代法消除递归末尾递归消除法3.算法设计(1)Fibonacci 数；Fibonacci(n) /递归算法if n=0 or n=1 thenreturn n;elsereturn Fibonacci(n-1) + Fibonacci(n-2) ;Fibonacci(n) /非递归算法if n=0 or n=1 thenreturn n;s1 = 0; s2 = 1;for i2 to n dosums1 + s2;s1s2;s2sum;return sum;(2)生成全排列； 问题分析- 分解：将原问题分解为n个子问题，子问题1：生成n-1个元素s1,sn-1的全排列后接sn;子问题2：生成n-1个元素s1,sn-2,sn的全排列后接sn-1; 子问题n：生成n-1个元素s2,sn的全排列后接s1;- 递归求解：子问题与原问题的性质相同，只不过规模为n-1。设原问题的求解算法为permute(s,n)，则子问题就是递归调用permute(s,n-1)。临界条件：一个元素的排列就是该元素本身。
