《算法导论》复习大纲DOC

1、1引言（chi）1.什么是算法及其特征算法（Algorithm ）是通过一个有限的指令序列集合对特定问题进行求解的一种计算执 行描述。算法特征：（1 ）输入：一个算法具有零个或多个取自指定集合的输入值；（2）输出：对每一次输入，算法具有一个或多个与输入值相联系的输出值；（3）确定性：算法的每一个指令步骤都是明确的；（4 ）有限性：对每一次输入，算法都必须在有限步骤（即有限时间）内结束；（5 ）正确性：对每一次输入，算法应产生出正确的输出值；（6 ）通用性：算法的执行过程可用于所有同类求解问题，而不仅适用于特殊输入。2.问题实例和问题规模问题实例是指需要计算同一个结果的问题的所有输入。问题规模是

2、指输入实例的大小，而输入实例是指问题的具体计算例子2算法初步（ch2）1.插入排序算法1）算法步骤：从左到右扫描数据 A，扫描到一个元素，将 Aj与其左边的元素从右到左依次比较，若比之小， 则将其之前元素后移，插入 A【j】，直至A【j】比他前面的元素大，扫描 A中的下一个元素 2 ）伪代码：In sertSort（A）for j=2 to A.le ngth第一层循环Key=Aji=j-1While i0 and aikey / 第二层循环Ai+1=Aii=i-1Ai+1=key算法设计与分析复习提纲2014.7.52.算法复杂性及其度量(1)时间复杂性和空间复杂性；(2)最坏、最好和平均情

3、形复杂性；顺序情况下 B (n) =O (n)、倒序情况下 W (n) =O (n2)、A (n) =0(n2)w(n)空间复杂性：需要常数个额外的临时空间存储临时数据2.插入排序的最坏、最好和平均时间最坏0(n2 2)、最好0(n)和平均时间0(n2 2),空间复杂度是 0(1)，稳定排序3.归并排序算法及其时间复杂性一时间E(n log n)1)算法步骤分解：分解待排序的 n个元素的序列为各具n/2个元素的两个子序列解决：适用归并排序递归的排序2个子序列合并：从左到有遍历 2个子序列，比较最前面的元素，将较小的元素移出子序列合并到上级序列的末尾， 循环进行上2步，直接所有元素都被合并到上级

4、序列，公进行r-p+1次；2)伪代码：MERGE-SORT(A,p,r)if pr q=向下取整(p+r) /2 MERGE-SORT(A,p,q);MERGE-S0RT(A,q+1,r)MERGE(A,p,q,r)MERGE(A,p,q,r)N1=q-p+1N2=r-q将A拆成长度分别为 N1、n2的2个子数组L,RL,R的末尾元素的后一个元素取值无穷大，作为哨兵；i=1，j=1 for k=p to rif Li=Rj Ak=Li i=i+1elseAk=Rjj=j+13函数增长率(ch3)1.渐近记号O、Q、B的定义及其使用1) 0渐进上界：0=f( n) %, f(n)的阶小与g(n)

5、的阶2)Q渐进下界：0=C(g( n) g, f(n) 的阶大与g(n)的阶3)渐紧界：0=C1(g( n) =f( n) g, f(n)的阶与g(n)的阶相等2.标准复杂性函数及其大小关系(1)多项式时间阶的大小0(1) O(log n) 0(n) 0(n*log n) 0(n2 ) 0(n3)(2)指数时间阶的大小0(2n) 0(n!) 证明2)对象限界最大最小项限界；几何级数限界；3)和式分解简单的一分为二；更复杂的划分；积分近似；4) Kn uth 求和：使用数学归纳法；使用摄动法；使用递归；使用积分；使用二重求和；使用有限演算；使用母 函数。4递归关系式(ch4)1.替换法(1)猜测

6、解数学归纳法证明；T( n) =2T(? n/2 ?)+n猜：T (n) = O(nlogn)证：2T(?n/2 ?)+n=Cnlogn 带入计算(2)变量变换法；T(n) =2T(?n1/2?)+log n令 m= logn,贝V, n=2 mT(2m)=2T(?2m -1 /2?)+m,令 S (m) =T(2m)贝U: S(m)=2S?m/2?+m 类似 T (n) =2T(?n/2 ?)+n=0(m log m)=0(log n log log n)2迭代法(1)展开法；T(1)=O(1)T (n) =3T(?n/4 ?)+n=n+3?n/4 ?+3 2?n/4 2?+ +3 KT(n

7、/4 K)总有 K，使得 1=n/4 K=2,即 K=1,b=1整数Casel f(n)= O(n log ba-?) = C n log ba-?贝V： T(n)= 0( n log b a)Case2 f(n)= C n log ba+? 且: af(n/b)=cf(n),对于常数 C=1 和足够大的 n 成立, 则 T(n)= 0( f(n)5堆排序(ch6)1堆的概念和存储结构堆是一种数据结构，堆是一个数组，近似完全二叉树，除最底层外，全部从左到右填充 满，对于序号为i的结点，其父结点的序号为i/2,其左孩子的序号为 2i,其右孩子序号为2i+1;0=A.heap-size=A .le

8、n gthn个元素的序列k1,k2,ki,，当且仅当满足下关系时， 称之为堆。(ki = k2i,ki = k2i,ki = k2i+1), (i = 1,2,3,4.n/2)堆的性质和种类大根堆：除根结点外，所有结点小于其父结点；用于堆排序、收益问题。 小根堆：除根结点外，父结点小于其所有结点；用于优先队列；成本问题；堆的操作：建堆；整堆；1)整堆算法：假设i的左右子树已经是大根堆，对i结点进行整堆，使其也是大根堆对调整的子树结点循环进行上2步骤，将小元素逐级下沉，直至满足堆特性；整堆时间复杂度0( log n )2)整堆伪代码Max-heapify(A,i) l=left(i)r=righ

9、t(i)if lAilargest=lelse largest=iif rAilargest=rif largestiexcha nge ai with largest max-heapify(A,largest)3)建堆算法因为从 A.heap-size/2+1 起到A.heapsize，都是叶子结点，故建堆可从A.heap-size/2到1整堆实现；算法复杂度 0 ( n)4)建堆伪代码Bulid_max_heap(A)heap-size=A .len gthfor i= ? A.heap-size /2? to 1Max-heapify(A,i)堆排序算法和时间复杂性算法思想：1)将数组

10、建堆2 )将根元素与结点 n交换并缩减堆的长度 13)对首元素整堆4)重复上述3个步骤，直至堆大小为1 (i=2时进行最后一次重复操作)时间复杂度O(n lg n )伪代码Heapsize(A)build_max_heap(A)For i=A.le ngth to 2Excha nge A1 to AiA.heap-size=A.heap-size-1max-heapfly(A,1)优先队列及其维护操作优先队列是维护集合S的数据结构，每个元素具有一个关键字key ;用于分支限界、搜索算法。支持如下操作：a)插入 insert(S,x)算法思想：1 )将元素插入末尾 Size+1的位置2)从插入

11、位置自底而上调整，使之满足堆性质算法复杂度O (log n )b)取最大关键字 Maximum(S)算法思想，输岀优先级最大的，也就是堆的根元素；c)删除并返回最大键值的元素Extract-max(S)算法思想：1)取堆根2)A1v-Aheap-sizeA3)heap-sizeA-4)对A1整堆时间复杂度0( log n )d)增值 元素x的关键字增加到k Increase-Key(S,x,k)算法思想：1) 如果Ai的关键字大于 K,则对i进行整堆；2) 否则，若i不是根结点且 K大于Ai的父结点，则交换 Ai与其父结点的关键字，并将K 值赋予其父结点。时间复杂度O(log n )6快速排序

12、(ch7)1.快速排序算法及其最好、最坏时间和平均时间快排采用分治法的思想，最好O(nlogn),最坏O(n2),平均O(nlogn)(1)分治法的基本思想分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。(2)快速排序的基本思想设当前待排序的无序区为Rlow.high，利用分治法可将快速排序的基本思想描述为： 分解：在Rlow.high中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间Rlow.pivotpos-1) 和Rpivotpos+1.high ，并使左边子区间中所

13、有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于 pivot.key ，而基准记录pivot则位于正确的位置(pivotpos) 上，它无须参加 后续的排序。Ap.r被划分为俩个(可能空)的子数组 Ap .q-1 和Aq+1 .r，使得Ap .q-1 = Aq = Aq+1 .r 求解：通过递归调用快速排序对左、右子区间Rlow.pivotpos-1 和Rpivotpos+1.high快速排序。3合并/快速排序void quick_sort(i nt s, int l, i nt r)if (l r)int i = l,

14、 j = r, x = sl;while (i j)while(i = x) /从右向左找第一个小于x的数j-；if(i j)si+ = sj;while(i j & si x) /从左向右找第一个大于等于x的数i+；if(i j)si = x;quick_sort(s, I, i - 1); /递归调用quick_sort(s, i + 1, r);2.随机快速排序算法及其期望时间期望时间负责度0( nlogn)算法描述：分解：以ap为基准元素将ap:r划分为3段ap:q-1,aq 和aq+1:r, 使ap:q-1 中任何一个元素小于等于aq，而aq+1:r中任何一个元素大于等于aq。下标q

15、在划分过程中确定。递归求解：通过递归调用快速排序算法分别对ap:q-1和aq+1:r进行排序。合并：由于对ap:q-1和aq+1:r的排序是就地进行的，所以在ap:q-1和aq+1:r都已排好的序后， 不需要执行任何计算，ap:r就已排好void Ra ndomizedQuickSort(double *a,i nt begi n,int end) /随机化快速排序if(begi nend)int p = Ran domizedPartiti on( a,begi n,en d);Ran domizedQuickSort(a,begi n,p-1);Ran domizedQuickSort(a

16、,p+1,e nd);in tRa ndomizedPartiti on( double*a,i ntbeg in ,i ntend) inti=Ra ndom(beg in,en d);double temp = ae nd;ae nd=ai;ai=temp;retur n Partiti on( a,begi n,en d);int Random( int m,int n ) /产生一个随机下表，用其对应的数组元素作为比较标准sran d(u nsig ned)time(NULL);return m+(ra nd()%( n-m+1);int Partiti on( double *a,i

17、 ntbegi n,i nt end)int i = beg in-1,j=beg in;double x = ae nd;while(je nd)if(aj=x) i+;double temp = ai;ai=aj;aj=temp;疋中; j+;double temp = ae nd;ae nd=ai+1;ai+1=temp;return i+1;7线性时间排序(ch8)1.基于比较的排序算法下界：Q (nlogn)证明：设h、丨分别代表判断树的高度和叶子树判定树是一颗二叉树丨 2h /叶子数不超过2h n! l logn! (nlogn) 证毕！2.计数排序适应的排序对象、算法和时间基本思

18、想：统计小于或等于 Ai的元素数目，将Ai置入相应的位置，即Ai -B小于或等于Ai的元素数目主要要解决的问题：?计数：统计小于或等于统计小于或等于 Ai的元素数目? 值相同元素的处理一种特殊情形的计数排序：问题：n个互不相同的整数A1.n , 1 Ai n, i=1n排序算法：SpecialCou ntin gSort(A,B)B1. n为排序结果for i 1 to n doBAi Ai; / 如 Ai=5，就放到 B5中时间：0(n)，无比较一般情形的计数排序：问题：n个可以相同的整数 A1.n ， 1 Ai 1对于十进制整数，nc需要的位数d=? log 10nc? +1 log 1n

19、 T(n)= 0 (d(n+k) =0 (nlogn)/k 为 10因此，不是线性时间排序 算法何时为线性时间？Idea:只要使d变为常数，k变大到与n同阶How to do How to do :选基k=n，贝U nc的位数为log nnc=c=dd=c， k=nT(n)= 0 (n)4.桶排序适应的排序对象、算法和时间假定：输入是均匀分布在0,1)上的实数。基本思想：0,1)划分为0,1/n),1/n,2/n),k/n,(k+1)/n),(n-1)/n,1)n个大小相等的子区间，每个子区间看作一个桶； 将n个元分配桶中； 对每个桶里的元素进行排序，依次连接桶；输入：0W A1. n v 1

20、0,1)0,n)即 k Ap.q-1三 AqAq+1.r；/Aq 为划分元K - q-p+1;/即Aq是第k个最小元If (i=k) then/ k=左区间长度+1return Aq ；lf(ik) then在右区间中继续找第i-k个元素；临界条件：当区间长度为1时，直接返回该元素Ran domizedSelect(A, p, r, i)/选择ith元素if p=r then return Ap;临界问题处理q Ran domizedPartiti on(A, p, r); k q-p+1;if i=k the n/进行划分并返回划分元的下标Aq是第k个小的元素Aq是i 元素T(n)T(n/5

21、) T(10n 6)(n/5向上取整)(n )ifn 140return Aq;else if i v k then/i 元素落在左区间retur n Ran domizedSelect(A, p, q-1, i);else/i th元素落在右区间retur n Ran domizedSelect(A, q+1, r, i-k);最好：每次划分为相等的左右区间T(n)=T(n/2)+n = T(n)=0 (n)最坏：每次划分为不均等的左右区间T(n)=T(n-1)+n = T(n)=0 (n 2)平均(期望)：分析略。T(n)= 0 (n)3.最坏时间为线性的选择算法及其时间分析算法步骤：Wh

22、ile n 1 dostep 1.将n个元素分成5个1组，共？ n/5 ?组。其中最后 1组有n mod 5个元素 step 2 .用插入排序对每组排序，取其中值。若最后 1组有偶数个元素，取较小的中值 step 3 .递归地使用本算法找找 ？n/5 ?个中值的中值x。step 4.用x作为划分元对 A数组进行划分，并设x是第k个最小元。step 5 . if i=k then return x;else if ix ?大于x的元素至少有 3(? ? n/5 ? /2 ? -2) 3n/10-6同理，小于 x的元素至少有 3n/10-6由上= 左区间和右区间的最大长度三7n/10+6运行时间递

23、归式的建立step 1 2: 0(1);step 3: T( ? n/5 ?);step 4: O(n);step 5:至多 T(7n/10+6)(1)ifn 140运行时间递归式的求解用替代法证：T( )n) cnT(n) c? n/5 ? +c(7n/10+6)+anc( n/5+1)+c(7 n/10+6)+a n=cn/5+c+7c n/10+6c+a n=9cn/10+7c+an=cn+(-c n/10+7c+a n)cn/a为常数/if -cn/10+7c+an 0要使-cn/10+7c+an 10an/(n-70)假定 n140，有 n/(n-70) v 2取 c 20a =-c

24、n/10+7c+an (2bh(x)-1 -1)+(2 bh(x)-1 -1)+1=2 bh(x)-1即第点得证。证明bh(rootT) h/2 , h为红黑树的树高红点的孩子必为黑/红黑树的性质4红点的层数vh/2因此= bh(rootT) h/2证明最后结论红黑树有n个内点 由= n 2bh(rootm) -1 2h/2 -1* = h r,则递归地在x的右子树中继续找第i-r个元素；时间：O(logn)(3) Rank问题的算法；求秩问题定义：OS树中，给定元素 x求其rank算法：step 1:在以 x 为根的子树中，x 的秩：r sizeleftx+1 ； r sizeleftx+1

25、 ；step 2:若x是根，则返回r;若x是双亲的左子，则 x在以px为根的子树 若x是双亲的左子，则 x在以px为根的子树中的秩是 r;若x是双亲的右子，则 x在以px为根的子树 p中的秩是r r+sezeleftpx+1 :x上移至px;重复 直 成立时 重复，直至成立时终止；时间：O(logn)(4)维护树的成本分析；1)OS树的维护：插入算法Phase 1 ：从根向下插入新节点将搜索路径上所经Phase 1 ：从根向下插入新节点，将搜索路径上所经历的每个节点的size+1 ,新节点的size置为1 ；-附加成本：O(log n) 附加成本：O(log n)Phase 2 :采用变色和旋

26、转方法，从叶子向上调整；-变色不改变size ； 变色不改变size ；-旋转可能改变size :旋转是局部操作旋转是局部操作，又，只有轴上的两个节点的size可能违反定义只需要在旋转操作后对违反节点size进行修改只需要在旋转操作后，对违反节点 size 进行修改-附加成本：旋转为 O(1)，总成本为O(logn)2)OS树的维护：删除算法Phase 1 ：物理上删除y在删除y时从y上溯至根将Phase 1 ：物理上删除y,在删除y时从y上溯至根，将所经历的节点的size均减1 ；-附加成本：O(log n) 附加成本：O(log n)Phase 2 :采用变色和旋转方法，从叶子向上调整；-

27、变色不改变size ； 变色不改变size ；-旋转可能改变size，至多有3个旋转；-附加成本：O(log n)-附加成本：O(log n)Remark：上面介绍的插入和删除均是有效维护有效，有效维护保证扩充前后的基本 操作的渐近时间不变。11递归与分治法(schl)1.递归设计技术递归的定义：若一个对象部分地包含它自己或用它自己给自己定若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调 用自己则称这个过程是递归的过程。递归有两种：直接递归：自己调用自己；间接递归：A调用B， B调用A递归方法的三种应用：以下三个方面常用到递归方法1、 递归定义

28、：如自然数定义：1是自然数；-一个自然数加1(后继)仍是自然数；注：“1 是自然数”是递归的临界条件2、 递归的数据结构：如，单链表节点是递归扩展的3、 问题的递归解法：如，汉诺塔问题的直观解法2.递归程序的非递归化示例：n!的递归和非递归算法Fact1( n)递归程序 if n=0 retur n 1;else return n *fact1( n-1);Remark :Fact2(int n)/非递归程序()序()非序 P=1;for i J 1 to n do p J p*i;return p;(1)递归算法易设计和分析，但执行效率较低，常要转化非递归程序;(2)递归算法的非递归实现通常

29、有三种实现方法：利用栈消除递归利用迭代法消除递归；末尾递归消除法3.算法设计(1)Fibonacci 数；Fib on acc i(n) /递归算法If n=0 or n =1 the nRetur n n;ElseRetur n Fib on acc i(n-1) + Fib on acc i(n-2) int fib(i nt n) II非递归算法int a = 1, b = 1;if(n=O | n=1) retur n n;for(i nt i=2; i1 ： T(n)=n*T(n-1)+0(n)得出 T(n)=0(n!)，该算法是最优的(3)二分查找1)基本思想：将有序序列(升序)等

30、分为几乎相等的两部分，待查关键字与划分元比 较。如果小于划分元，则递归处理左半部分，否则递归处理右半比较。非递归算法：Bi S h1(L )/找到x返回下标值，找不到返回-1left J 1, right J n; flag J 0; /flag 为标志变量while (left w right and flag=0) do while (left w right and flag=0) do mid J (left+right)/2;(此处有最小下界符号)if x=Lmid then flag J 1; if x=Lmid then flag J 1;else if x v Lmid the

31、n right J mid-1;else leftJ mid+1;if flag=1 the n retur n mid;else return -1; 2)递归算法：Bin arySearch2(L ,x,i, j) y(,j)在有序表Li.j中查找xIf i j then return -1;If i=j the nif x=Li the n retur n i;else return -1;else mid -(i+j)/2;/ (此处有最小下界符号)if x=Lmid the n retur n mid;if x=Lmid the n retur n mid;else if x v L

32、mid thenreturn Bin arySearch2(L, x, i, mid-1);else return Bin arySearch2(L, x, mid+1, j);3)递归算法时间分析N=1 : T(n)=O(1) ； n1 : T(n)= T(n/2)+O(1)得出 T(n)=O(logn)(4)大整数乘法1)普通递归乘法分析：X、Y是n位的二进制数，设 X是n/2位的A+ n/2位的B ； Y 是n/2位的C+ n/2位的D则 X=A2 n/2+B, Y=C2 n/2+D 则 XY=AC2 n+(AD+BC) 2 n/2+BD;其计算成本：T(n)=0(n 2)2)改进的分治

33、乘法：X=A2 n/2+B,Y=C2 n/2+D,贝U : XY =AC2 n+(A-B)(D-C)+AC+BD)2n/2+BD ，则T(n)=O(n log3)=O(n1.59)Stranssen矩阵乘法把C=A x B写为2 x 2的分块矩阵令 P=(A11+A22 )(B11 +B22 ); Q=(A21+A22)B11 ; R=A11(B12-B22) ; S=A22(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12),V=(A12-A22)(B21+B22)则C 1仁P+S-T+V; C12=R+T ; C21=Q+S; C22=P+R-Q+U时间分

34、析：n=2:T(n)=O(1);n2:7T(n/2)+O(n 2)T(n)=O(n log7)O(n2.81)目前最好的计算时间上界是O(n2.367)，而最好下界仍是Q (n2)。12动态规划(ch15)1.方法的基本思想和基本步骤动态规划的思想实质 是分治思想 和解决冗余。如果能够保存已解决的子问题的答案，在需要时再查找，这样就可以避免重复计算、节省时间。 动态规划法用一个表来记录所有已解的子问题的答案。 这就是动态规划法的基本思路。具体的动态规划算法多种多样具体的动态规划算法多种多样，但它们具有相同的填表方式动态规划法的有效性依赖于问题本身所具有的两个重要的适用性质最优子结构和重叠子问题

35、 找岀最优解的性质，并刻画其结构特征; 递归地定义最优值(写出动态规划方程) 以自底向上的方式计算岀最优值； 根据计算最优值时记录的信息，构造最优解。注：-步骤是动态规划算法的基本步骤。如果只需要求岀最优值的情形，步骤可以省略;-若需要求岀问题的一个最优解，则必须执行步骤，步骤中记录的信息是构造最优解的基 础2.动态规划和分治法求解问题的区别与分治法类似的是：将原问题 分解成若干个子问题，先求解子问题，然后从这些子问题的解得到 原问题的解。与分治法不同的是 经分解的子问题往往不是互相独立的。若用分治法来解，有些共同部分(子问题或子子问题)被重复计算了很多次。3.最优性原理及其问题满足最优性原理

36、的证明方法例1:设G是一个有向加权图，则G从顶点i到顶点j之间的最短路径问题满足最优性原理。证明：(反证)设iipiqj是一条最短路径，但其中子路径 ipiqj不是最优的， 假设最优的路径为ipiq j则我们重新构造一条路径：iipiq j显然该路径长度小于iipiqj，与iipiqj是顶点i到顶点j的最短路径相矛盾.所以，原问题满足最优性原理。0-1背包问题Knap(1,n,c)满足最优性原理(证明略)最长路径问题不满足最优性原理(证明略)动态规划的设计技巧：阶段的划分、状态的表示和存储表的设计；问题的阶段划分和状态表示，需要具体问题具体分析，没有一个清晰明朗的方法； 空间溢岀的问题，是动态

37、规划解决问题时一个普遍遇到的问题；4.算法设计(1)多段图规划；问题描述：多段图 G=(V, E)是一个有向图，且具有以下特征：(1)划为k 2个不相交的集合 Vi, 1 i k ；(2)V1和Vk分别只有一个结点 s(源点)和t(汇点)；(3)若 E(G)，u Vi ，贝U v Vi + 1 1 i k,边上成本记 c(u,v)；若 E(G)，边上成本记 c(u,v) =8;求由s到t的最小成本路径。MultiStageGraph( G, k, n, p)/输入n个结点的k段图，假设顶点按段的顺序编号E(G)是边集，p1.k是最小成本路径new cost n;/生成数组cost, costj

38、相当于前面的 cost(i,j)new dn;/生成数组d, dj保存vj与下一阶段的最优连接点cost n=0;for i=n-1 dwonto 1do/ 计算 costi和 dicosti=OO ;while(任意 E(G)/r是下一阶段中的顶点if(c(i,r)+costrcosti) costi=c(i, r)+costr; di=r;p1=1； pk=n;/以下是找一条最小成本路径(构造解)for i=2 to k-1 dopi=dpi-1； T(n)=0(n+e)(2)矩阵链乘法；问题描述：给定 n个矩阵A1,A2,An , Ai的维数为pi-1 x pi(1 i sum) sum

39、=thissum;besti=i; bestj=j;return sum;注：原算法：T(n)=O(n3);思考题：对k循环可以省略，改进后的算法：T(n)=O(n2);二、分治算法基本思想：将 A仁n分为a仁n/2和an/2+仁n，分别对两区段求最大子段和，这时有三种情形：Case 1a1. .n的最大子段和的子段落在a1. n/2；Case 2a1. .n的最大子段和的子段落在an /2. n；Case 3a1. .n的最大子段和的子段跨在a1.n/2和 an/2.n之间;时间复杂度：T(n)(nlog gn)int sum=0, b=0;for(i nt j=1; j=n; j+) /s

40、um存储当前最大的bj, b 存储 bjb += aj;if(bsum) the n sum=b;/ bj运行时间:对C Case 1和C Case 2可递归求解；对 Case 3，可知an/2和an/2+1 定在最大和 的子段中，因此在 a仁n/2 中计算S1，在an/2.n 中计算S2, S1+S2是Case3的最大 值MaxSubSum2(a, left, right) /返回最大子段和sum=0;if( left=right )sum=aleftO?aleft:O;else cen ter=(left+right)/2; leftsum=MaxSubSum2(a, left,ce nt

41、er); rightsum=MaxSubSum2(a, cen ter+1, right); s1=0; leftmidsum=O;for i=ce nter to left do leftm in sum += ai;if (leftmidsums1) the n s1=leftmidsum;s2=0; rightmidsum=0;for i=ce nter+1 to right do rightm in sum += ai; if(rightmidsums2) the n s2=rightmidsum;sum=s1+s2;if(sumleftsum) the n sum=leftsum;

42、if(sum zk=xm=yn 且 Zk-1 是 Xm-1 和 Yn-1 的一个 LCS;(2)若 xmyn 且 zkxm, = Z 是 Xm-1 1 和 丫丫 的一个 LCS;(3)若 xmyn 且 zkyn, = Z 是 X 和 Yn-1 的一个 LCS;注：由此可见，2个序列的最长公共子序列可由(1)(2)(3)算岀，(2)(3)的解是对应子问题的最优解。因此，最长公共子序列问题具有最优子结构性 质。证明： 若 xm=y yn, = zk=x xm=y yn 且 Zk k-1 1 是 Xm m-1 1 和 Yn n-1 1 的一个 LCS; (应用反证法)先证： zk=xm=yn。若zk

43、xm (也有Zkyn ),则将xm加到Z后，于是获得 X和y的长度为k+1的CS,与 Z 是 X 和 丫丫 的 LCS矛盾。 = zk=xm=yn再证：Zk-1是Xm-1和Yn-1的一个LCS。由Z的定义= 前缀Zk-1是Xm-1和Yn-1的CS(长度为k-1)若Zk-1不是Xm-1和Yn-1的LCS,则存在一个 Xm-1和Yn-1的公生的公共子序列长度k k，与Z是X和Y的LCS矛盾。= Zk-1 是Xm-1和Yn-1的一个LCS(2)若 xmyn 且 zkxm, = Z 是 Xm-1 和 Y 的一个 LCS;/ zkxm，贝U Z 是 Xm-1 和 Y 的一个 CS 下证：Z是Xm-1和Y

44、的LCS(反证)若不然，则存在长度k的CS序列 W显然，W也是X和Y的CS,但其长度kk，矛盾。(3)若 xmyn 且 zkyn, = Z 是 X 和 Yn-1 的一个 LCS;()与对称，类似可证。综上，定理15.1证毕。子问题的递归解(step2 )定理15.1将X和Y的LCS分解为：(1)if xm=y n the n/解一个子问题找 Xm-1 和 Yn-1 的 LCS;(2)if xmyn the n/解二个子问题找Xm-1和Y的LCS和 找X和Yn-1的LCS;取两者中的最大的；ci,j 定义为 Xi 和 Yj 的 LCS长度，i=Om, j=0n ；j0,=0 GF j =0iJ0

45、 anddxi = yjmaxc2j-lzc2-ljij 0 andxtoyj计算最优解值(step3 )LCS_Le ngth(X, Y) m len gthX; n len gthY;for i 0 to m do ci,0 0;/o列for j 0 to n do c0,j 0;/o行“T” ; / 由 Xi-1 和 Yj “” ; / 由 Xi 和 Yj-1for i 1 to m dofor j 1 to n doif xi=y yj the n ci, j ci-1, j-1 +1; bi, jelseif ci-1, j=ci, j-1 the n ci, j ci-1, j;

46、bi, j确定else ci, j ci, j-1; bi, j确定return b and c; 时间：e (mn)构造一个 LCS (step4 )Prin t_LCS(b, X, i, j) if i=0 or j=0 the n retur n;if bi,j=” the n Prin t_LCS(b, X, i-1, j-1);pri nt xi;elseif bi,j=“T”then Print_LCS(b, X, i-1, j);else Prin t_LCS(b, X, i, j-1);时间：e (m+n)13贪心算法（ch16）1方法的基本思想和基本步骤（1）贪心法的基本思想

47、贪心算法是根据一种贪心准则 （greedy criterion）来逐步构造问题的解的方法。在每个阶段，都作出了相对该准则最优的决策。决策一旦作出，就不可更改。由贪心法得到的问题的解可能是最优解，也可能只是近似解。能否产生问题的最优解需要加以证明。所选的贪心准则不同，则得到的贪心算法不同，贪心解的质量当然也不同。 因此，贪心算法的好坏关键在于正确的选择贪心准则。（2）设计贪心算法的基本步骤（1 ）选定合适的贪心选择的标准；（2） 证明在此标准下该问题具有贪心选择性质；（3） 证明该问题具有最优子结构性质；（4） 根据贪心选择的标准，写出贪心选择的算法，求得最优解。2.贪心算法的正确性保证：满足贪

48、心选择性质贪心选择性质：可通过局部最优（贪心）选择达到全局最优解。-通常以自顶向下的方式进行，每次选择后将问题转化为规模最小的子问题；-该性质是贪心法使用成功的保障，否则得到的是近优解3贪心算法与动态规划的比较（1）相同点：动态规划算法和贪心算法都属于递推算法，并且这两个算法适用的问题都具有最优子结构，都利用局部最优解来推导全局最优解。（2）不同点：动态规划算法和贪心算法有一个显著区别：_1）在动态规划算法中，以自底向上的方式来利用最优子结构，也就是说，首先找到子问 题的最优解，解决子问题，然后找到问题的一个最优解。2） 在贪心算法中，以自顶向下的方式使用最优子结构，也就是说，贪心算法会先做出

49、选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先求解子问题的最优解，然后再做出选择。两者的不同点：1贪心算法作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一一步的最优解，而上一部之前的最优解则不作保留。2动态规划算法的全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有局部最优解；4.两种背包问题的最优性分析：最优子结构性质和贪心选择性质1）贪心选择性质：可通过局部最优（贪心）选择达到全局最优解。-通常以自顶向下的方式进行，每次选择后将问题转化为规模最小的子问题；-该性质是贪心法使用成功的保障，否则得到的是近优解2）最优

50、子结构性质：问题的最优解包含它的子问题的最优解-并不是所有具有最优子结构性质的问题都可以采用贪心策略-往往可以利用最优子结构性质来证明贪心选择性质。5.算法设计（1）小数背包；允许将小数表示的物品放入背包中的是小数背包问题。举例来说，如果物品是原油、飞机燃料、煤油而你的背包是一只水桶，取0.473升的原油，0,263升的飞机燃料和0,264升的煤油就是有意义的。这是形式最简单的要解决的背包问题。小数背包问题是三者中最简单的，其贪婪解法如下：?找到“值密度”（物品值/尺寸）最大的物品?如果总容量仍就超过物品的可利用率，把所有满足条件的物品放入背包中，然后反复执行。?如果总容量少于物品的可利用率，

51、尽可能多的使用可用空间，然后终止。?由于这个算法必须先按照值密度把物品分类，然后以降序将它们放入背包，直至容量用完，?该算法以 Nlog N 级运行。通常简单些的方法不是将它们分类，而是不停地找每次不用的最大值密度，这种算法的时间复杂度是0（2）问题：求一定背包容量情况下，装入价值最多的东西Wi:重量vi:价值 Vi/Wi :价值率（单位重量价值）GreedyK napsack（ n,M,w,w,x）/按价值率最大贪心Sort （ n,v,w ） ;/ 使 V1/W1=V2/W2=.=Vn/wnFor i=1 to n do xi=0;c=M;For i=1 to n dolf（wic） br

52、eak;Xi=1; c- = wi;If（i= n） xi=c/wi;物品i是选择的最后一项例：设待安排的i 1234Si1 3 0fi4 5 6算法 greedySelector5678910115356882127891011121314T (n) =0(nlogn)(2)活动安排；1问题有n件任务和一台机器，任务可在机器上得到处理。每件任务j的开始时间为sj ,完成时间为fj，sjfj ，即sj,fj为处理任务j的时间范围。规定机器在任何时刻最多只处理一件任务，且一件任务的处理不允许间断，要连续处理直到结束。要求找出一种安排任务的方案，使得该机器能完最多数目的任务。2 求解思想贪心准则：

53、每次从剩下未安排的任务中选择具有最小的完成时间且不会与现有的任务重 叠的任务来安排。贪心算法：先将任务按完成时间从小到大排序。即fl f2 ww fn。然后依此次序来考虑任务的安排(即按贪心准则来安排)，一旦某个任务考虑过了，即从剩余任务中去掉。时间复杂度：O(nlogn)。3.活动安排问题的贪心算法GreedySelector :templateclass Typevoid GreedySelector(int n, Type s, Type f, bool A)/各活动的起始和结束时间存储于数组s和f中，且按结束时间的非减序排列A1=true;int j=1;for (i nt i=2;i

54、=fj) Ai=true; j=i; else Ai=false;3.算法 GreedySelector 分析：由于输入的活动以其完成时间的非减序排列，所以算法greedySelector 每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算 法只需0(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出 的活动未按非减序排列，可以用 0(nlo

55、gn)的时间重排。11个活动的开始时间和结束时间按结束时间的非减序排列如下:的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动14回溯法(sch2)1方法的基本思想和基本步骤1)方法的基本思想回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点岀发搜索解空间树。系统性算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不 包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继 续按深度优先的策略进行

56、搜索。一一跳跃性2)基本步骤(1) 针对问题，定义问题的解空间(对解进行编码)；(2) 确定易于搜索的解空间组织结构(按树或图组织解)；(3) 以深度优先方式搜索解空间，搜索过程中裁减掉死结点的子树提高搜索效率。2.回溯法是一种深度遍历的搜索3术语：三种搜索空间，活结点，死结点，扩展结点，开始结点，终端结点 三种搜索空间：-表序表示：搜索对象用线性表数据结构表示；-显式图表示：搜索对象在搜索前就用图(树)的数据结构表示；-隐式图表示：除了初始结点，其他结点在搜索过程中动态生成缘于搜索空 间大，难以全部存储.活结点：已生成一个以上子节点，但所有子结点尚未全部生成的结点 死节点：不在进一步扩展或已

57、产生了所有子结点的结点。扩展节点:一个正在产生儿子的结点称为扩展结点开始节点：根节点终端节点：叶节点4.两种解空间树和相应的算法框架(1)子集树回溯算法框架Backtracknt t)/搜索到树的第t层/由第t层向第t+1层扩展，确定xt的值if tn then output(x);/叶结点是可行解，输岀解else while( all Xt) do/ Xt为所有xt的合法取值集 xt= Xt 中第i个值；if( Con strai nt(t) and Bou nd(t)Backtrack(t+1);执行时：Backtrack(l) /从1扩展并回溯(2)排列树回溯算法框架Backtrack(

58、int t)/搜索到树的第t层/由第t层向第t+1层扩展，确定xt的值if tn then output(x);/叶结点是可行解，输岀解elsefor i=t to n do swap(xt, xi);if( Con strai nt(t) and Bou nd(t)Backtrack(t+1);swap(xt, xi);5算法设计1)二叉树的遍历(1)先序遍历Preorder(BiTree T)/递归程序if T!=nil the n visit(T);Preorder(T-lchild);Preorder(T-rchild);=以下为非递归=Preorder(BiTree T)/非递归程序

59、if T=nil the n retur n;in istack(S); push(S, T); while(!empty(S) do BiTree p=pop(S); while(p!=nil) do visit(p); push(S, p-rchild); p=p-lchild;(2)按层次遍历BFSorder(BiTree T)if T=nil the n retur n;iniq ueue(Q); enq ueeu(Q, T); while(!empty(Q) do BiTree p=Dequeue(Q);visit(p);if p-lchild != nil the n enq ue

60、ue(Q, p-lchild); if(p-rchild!=NIL) enq ueue(Q, p-rchild);2)图的遍历(1)深度优先搜索DFS(vo) vo.visited=True;while(所有与 vo 邻接的顶点 v and !v.visited ) do DFS(v);return;DFS 序列：ABDHEFCG(2)广度优先搜索BFS(v) iniq ueue(Q); enq ueue(Q, vc); while( !empty(Q) ) do p=dequeue(Q);p.visited=True;while(所有与p邻接的顶点v & !v.visited ) do en