第1章渐增型算法徐子珊

第1章集腋成裘渐增型算法1.1算法设计与分析1．什么是算法算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。2．算法分析基本概念算法运行所需要的计算机资源的量称为算法的复杂性。计算算法运行所需资源量的过程称为算法复杂性分析，简称为算法分析。理论上，算法分析既要计算算法的时间复杂性，也要计算它的空间复杂性。本书中除非特别说明，所说的算法分析，仅局限于对算法的时间复杂性分析。随机访问计算机RAMRAM只用一个处理机，却有无限量的随机存储器。它的有限个基本操作——算术运算、逻辑运算和数据的移动（比如对变量的赋值）均在有限固定时间内完成，假定所有这些基本操作都消耗一个时间单位。算法在RAM上运行所需的时间，显然就是执行基本操作的次数。算法运行时间的3种情形对固定的输入规模，使运算时间最长的输入所消耗的运行时间称为算法的最坏情形时间。对固定的输入规模，使运行时间最短的输入所消耗的时间，称为最好情形时间。假定固定的输入规模为n，所有不同输入构成的集合为Dn，对问题的每一个输入为IDn，若已知该输入发生的概率为P(I)，对应的运行时间为T(I)，运行时间的数学期望值称为算法的平均情形时间。3．实例在线性表A中查找。（a）查找值为x=1的元素，从A[1]起依次要进行5次检测，第一次找到值为1的元素。（b）查找值为x=11的元素，从A[1]起依次检测完所有元素（进行10次检测），没有找到值为11的元素——最坏情形。（c）查找值为x=3的元素，从A[1]起仅进行一次检测就找到值为3的元素——最好情形。4．算法的渐进运行时间当n时，评估T（n）趋于无穷大的快慢来分析算法的时间复杂性。我们往往用几个函数Ỹ（n）：幂函数nk（k为正整数）、对数幂函数lgkn（k为正整数，底数为2）和指数函数an（a为大于1的常数）作为“标准”，研究极限：若λ=非零常数，则称Ỹ（n）是T（n）的渐近表达式，或称T（n）渐近等于Ỹ（n），记为T（n）=Θ（Ỹ（n）），这个记号称为算法运行时间的渐近Θ-记号，简称为Θ-记号。5．有效算法如果两个算法运行时间的渐近表达式相同，则将它们视为具有相同时间复杂度的算法。显然，渐近时间为对数幂的算法优于渐近时间为幂函数的算法，而渐近时间为幂函数的算法则优于渐近时间为指数函数的算法。我们把渐近时间为幂函数的算法称为是具有多项式时间的算法，渐近时间不超过多项式的算法则称其为有效的算法。6．渐增型算法渐增型算法有一个共同的特征：构成算法的主体是一个循环结构，它逐步将部分解扩张成一个完整解。该循环将遵循一个始终不变的原则：每次重复之初，总维持着问题的一个部分解。我们将此特征称为算法的循环不变量。1.2插入排序算法1．问题的理解与描述排序问题的形式化表示为：输入：一组数<a1,a2,...,an>。输出：输入的一个排列（重排）<a'1,a'2,...,a'n>，满足a'1a'2,...,a'n。2．算法的伪代码描述INSERTION-SORT（A）1forj←2tolength[A]2 dokey←A[j]3 将A[j]插入到排好序的序列A[1…j-1]中。4 i←j-15 whilei>0andA[i]>key6 doA[i+1]←A[i]7 i←i-18 A[i+1]←keyINSERTION-SORT在A=<7,4,6,8,3,5>上的操作数组的下标表示在各方格的上方，存储在数组中的数值表示在各方格内。（a）～（e）第1～8行的for循环的各次重复。每次重复中，黑色方格放的是键A[j]，它在第5行中逐一与其左边灰色方格内的元素比较。灰色的箭头指示处在第6行中被右移一格的元素，黑色箭头则指示出键在第8行移动到的位置。（f）最终排好序的数组。3．算法的正确性循环不变量第1～8行的for循环的每次重复之初，子序列A[1…j-1]由原来A[1…j-1]中的元素组成，且已排好序。

4．算法的运行时间假定序列A含有n个元素，对INSERTION-SORT而言，最坏情形是序列A初始状态是降序排列。在此情形下，对第1～8行的for循环的n-1次重复的每一次，内嵌的第5～7行的while循环将分别重复1，2，…，n-1次。所以，第6～7行的操作将重复进行1+2+…+n-1=n（n-1）/2次。于是，该算法的最坏情形时间用Θ-记号表示为Θ(n2)。1.3两个有序序列的合并算法1．问题的理解与描述将两个有序序列合并为一个有序序列问题的形式化表示为：输入：序列A[p…r]。其中，子序列A[p...q]和A[q+1...r]是有序的。输出：A[p...r]所有元素的重排，使之有序。2．算法的伪代码描述MERGE(A,p,q,r)1n1←q-p+12n2←r-q3创建数组L[1…n1]和R[1…n2]4fori←1ton15 doL[i]←A[p+i-1]6forj←1ton27 doR[j]←A[q+j]8i←19j←110

k←p11whilei

n1andjn212 doifL[i]R[j]13 thenA[k]←L[i]14 i←i+115 elseA[k]←R[j]16 j←j+117 k←k+118ifi<n119 then将L[i...n1]复制到A[k...r]20ifj<n221 then将R[j...n2]复制到A[k...r]对序列A[9..16]=<2,4,5,7,1,2,3,6>运行MERGE过程使用两个辅助数组L和R进行合并操作。在复制后，数组L包含<2,4,5,7>，数组R包含<1,2,3,6>。A中深灰色的位置包含最终值，L和R中浅灰色位置包含的值尚未复制回A中。A的浅灰色位置是将被覆盖的，而L和R中深灰色位置包含的是已经被复制回A的值。(a)～(g)是第12～17行的while循环每次重复之初的A、L、R及其下标k、i、j。(h)是执行了第18～21将L中剩余的元素复制到A[k...r]中。此时，子数组A[9…16]已经排好序。3．算法的正确性循环不变量：在第12～17行的while循环的每次重复之初，子数组A[p…k-1]包含L[1…n1]和R[1…n2]中的k-p个最小的元素，并排好序。此外，L[i]和R[j]分别是各自数组中尚未复制回数组A的元素中的最小者。可利用此循环不变量来证明合并算法MERGE是正确的。1.4序列的划分1．问题的理解与描述序列的划分问题描述如下：输入：序列A[p…r]。输出：下标q（p

q

r），原序列A[p…r]的一个重排：使得A[p…q]中的元素值不超过A[q](=原A[r]的值)，而A[q+1...r]中的元素值均大于A[q]。2．算法的伪代码描述PARTITION(A,p,r)1x←A[r]2i←p-13forj←ptor-14 doifA[j]

x5 theni←i+16 exchangeA[i]↔A[j]7exchangeA[i+1]↔A[r]8returni+1对一个样本序列的划分操作（a）初始的序列和变量设置。没有任何元素进入上述两部分。（b）～（h）表示第3～6行的for循环的每一次重复。黑色双向箭头表示第6行的元素交换操作。（i）表示上述循环终止后第7行执行的元素交换操作。3．算法的正确性循环不变量：在第3～6行的for循环的每次重复之初，对每一个数组下标k，若p