第 1 章 渐增型算法 徐子珊

1、第1章 集腋成裘 渐增型算法1.1 算法设计与分析 1什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 2算法分析基本概念 算法运行所需要的计算机资源的量称为算算法的复杂性法的复杂性。 计算算法运行所需资源量的过程称为算法复杂性分析，简称为算法分析算法分析。 理论上，算法分析既要计算算法的时间复杂性，也要计算它的空间复杂性。 本书中除非特别说明，所说的算法分析，仅局限于对算法的时间复杂性分析。 随机访问计算机 RAM RAM只用一个处理机，却有无限量的随机存储器。

2、它的有限个基本操作算术运算、逻辑运算和数据的移动（比如对变量的赋值）均在有限固定时间内完成，假定所有这些基本操作都消耗一个时间单位。 算法在RAM上运行所需的时间，显然就是执行基本操作的次数。 算法运行时间的3种情形 对固定的输入规模，使运算时间最长的输入所消耗的运行时间称为算法的最坏情形时间最坏情形时间。 对固定的输入规模，使运行时间最短的输入所消耗的时间，称为最好情形时间最好情形时间。 假定固定的输入规模为n，所有不同输入构成的集合为Dn，对问题的每一个输入为IDn，若已知该输入发生的概率为P(I)，对应的运行时间为T(I)，运行时间的数学期望值 称为算法的平均情形时间平均情形时间。3实例

3、在线性表A中查找。（a）查找值为x=1的元素，从A1起依次要进行5次检测，第一次找到值为1的元素。（b）查找值为x=11的元素，从A1起依次检测完所有元素（进行10次检测），没有找到值为11的元素最坏情形。（c）查找值为x=3的元素，从A1起仅进行一次检测就找到值为3的元素最好情形。 4算法的渐进运行时间 当n时，评估T（n）趋于无穷大的快慢来分析算法的时间复杂性。我们往往用几个函数（n）：幂函数nk（k为正整数）、对数幂函数lgkn（k为正整数，底数为2）和指数函数an（a为大于1的常数）作为“标准”，研究极限： 若=非零常数，则称（n）是T（n）的渐近表达式，或称T（n）渐近等于（n），记

4、为 T（n）=（n），这个记号称为算法运行时间的渐近-记号，简称为-记号。 )()(limnTnYn5有效算法 如果两个算法运行时间的渐近表达式相同，则将它们视为具有相同时间复杂度的算法。显然，渐近时间为对数幂的算法优于渐近时间为幂函数的算法，而渐近时间为幂函数的算法则优于渐近时间为指数函数的算法。我们把渐近时间为幂函数的算法称为是具有多项式时间的算法多项式时间的算法，渐近时间不超过多项式的算法则称其为有效的算法有效的算法。 6渐增型算法 渐增型算法渐增型算法有一个共同的特征：构成算法的主体是一个循环结构，它逐步将部分解扩张成一个完整解。该循环将遵循一个始终不变的原则：每次重复之初，总维持着问

5、题的一个部分解。我们将此特征称为算法的循环不变量循环不变量。 1.2 插入排序算法 1问题的理解与描述 排序问题的形式化表示为： 输入输入：一组数。 输出输出：输入的一个排列（重排），满足a1a2, ., an。2算法的伪代码描述 INSERTION-SORT （A） 1 for j 2 to lengthA 2 do key Aj 3 将Aj插入到排好序的序列A1 j - 1中。 4 i j - 1 5 while i 0 and Ai key 6 do Ai + 1 Ai 7 i i - 1 8 Ai + 1 keyINSERTION-SORT在A = 上的操作46783512345674

6、6835123456476835123456467835346785345678(a)(b)(c)(d)(e)(f)数组的下标表示在各方格的上方，存储在数组中的数值表示在各方格内。（a）（e）第18行的for循环的各次重复。每次重复中，黑色方格放的是键Aj，它在第5行中逐一与其左边灰色方格内的元素比较。灰色的箭头指示处在第6行中被右移一格的元素，黑色箭头则指示出键在第8行移动到的位置。（f）最终排好序的数组。 3算法的正确性 循环不变量循环不变量 第第18行的行的for循环的每次重复之初，子序循环的每次重复之初，子序列列A1j - 1由原来由原来A1j - 1中的元素组中的元素组成，且已排好序

7、。成，且已排好序。 4算法的运行时间 假定序列A含有n个元素，对INSERTION-SORT而言，最坏情形是序列A初始状态是降序排列。在此情形下，对第18行的for循环的n-1次重复的每一次，内嵌的第57行的while循环将分别重复1，2，n-1次。所以，第67行的操作将重复进行1+2+n-1=n（n-1）/2次。于是，该算法的最坏情形时间用-记号表示为(n2)。1.3 两个有序序列的合并算法 1问题的理解与描述 将两个有序序列合并合并为一个有序序列问题的形式化表示为： 输入输入：序列Apr。其中，子序列Ap.q和Aq+1.r是有序的。 输出输出：Ap.r所有元素的重排，使之有序。2算法的伪代

8、码描述MERGE(A, p, q, r)1 n1q - p + 12 n2 r - q3创建数组L1n1和R1n24 for i 1 to n15 do Li Ap + i - 16 for j 1 to n27do Rj Aq + j8 i 19 j 110 k p11 while i n1 and j n212 do if Li Rj13then Ak Li14 i i + 115 else Ak Rj16j j + 117 kk+118 if i n119 then 将Li. n1复制到Ak.r20 if j n221 then 将Rj. n2复制到Ak.r对序列A9.16 = 运行ME

9、RGE过程使用两个辅助数组L和R进行合并操作。在复制后，数组L包含，数组R包含。A中深灰色的位置包含最终值，L和R中浅灰色位置包含的值尚未复制回A中。A的浅灰色位置是将被覆盖的，而L和R中深灰色位置包含的是已经被复制回A的值。(a)(g)是第1217行的while循环每次重复之初的A、L、R及其下标k、i、j。(h)是执行了第1821将L中剩余的元素复制到Ak.r中。此时，子数组A916已经排好序。 2457123624571236LRkijA1457123624571236LRkijA1257123624571236LRkijA1227123624571236LRkijA1223423624

10、571236LRkijA1223453624571236LRkijA1223456624571236LRkijA1223456724571236LRkijA(a)(b)(c)(d)(f)(e)(g)(h)981011121314151617123412349810111213141516171234123498101112131415161798101112131415161712341234123412349810111213141516179810111213141516171234123412341234981011121314151617123412349810111213141516

11法的正确性 循环不变量：循环不变量： 在第在第1217行的行的while循环的每次重复之初，循环的每次重复之初，子数组子数组Apk - 1包含包含L1n1和和R1n2中的中的k - p个最小的元素，并排好序。此外，个最小的元素，并排好序。此外，Li和和Rj分别是各自数组中尚未复制回数分别是各自数组中尚未复制回数组组A的元素中的最小者。的元素中的最小者。 可利用此循环不变量来证明合并算法可利用此循环不变量来证明合并算法MERGE是正确的。是正确的。1.4 序列的划分 1问题的理解与描述 序列的划分问题描述如下： 输入输入：序列Apr。 输出输出：下标q（p q r），原序

12、列Apr的一个重排：使得Apq中的元素值不超过Aq(=原Ar的值)，而Aq+1.r中的元素值均大于Aq。2算法的伪代码描述 PARTITION(A, p, r) 1 x Ar 2 i p - 1 3 for j p to r - 1 4 do if Aj x 5 then i i + 1 6 exchange Ai Aj 7 exchange Ai + 1 Ar 8 return i + 1对一个样本序列的划分操作 （a）初始的序列和变量设置。没有任何元素进入上述两部分。（b）（h）表示第36行的for循环的每一次重复。黑色双向箭头表示第6行的元素交换操作。（i）表示上述循环终止后第7行执行的元素交换操作。 82713564prij82713564p irj82713564p irj82713564p irj12783564prji12387564prji12387564prji12387564prji12387564prji(a)(b)(c)(d)(e)(f)(g)