2012操作系统习题

习题

1、2 n+1=O(2n)成立吗？2 2n=O(2n)成立吗？ 2、证明O(f)+O(g)=O(max(f,g)) 3、证明：n!=o(nn)

4、下面的算法段用于确定n的初始值。试分析该算法段所需计算时间的上界和下界。 While(n>1)

If (odd(n)) n=3*n+1 else

n=n/2;

解：平均复杂度：log(2,n)+log(2,3^k)=log(2,n)+k*log(2,3*n) 最小复杂度：log(2,n),当n=2^m,只执行第2句， 最大复杂度：k*log(2,3*n);n约等于[log(2,n*3^k)] 5、画出T(n)=T(n/3)+T(2n/3)+3的递归树。 T(n)= T(n/3)+ T(2n/3)+n 的地归树如下：

Mathematical Induction 数学归纳法

使用数学归纳法，这个大家基本都清楚，就是假设一个在n的时候结论成立，证明在n+1的时候结论也成立，当然，在我们这里，稍微有点变化。举个例子。 T(n) = T(n/2) + T(n/4) + T(n/8) + n

现在我们要就上面表达式T(n)，现在我们就先guess T(n) = Theta(n)。 当然我们知道要证明T(n) = Theta(n)，我们需要分别证明T(n) = O(n)和T(n) = Omega(n)。 很显然，这里T(n) = Omega(n)的，因为T(n) = T(n/2) + T(n/4) + T(n/8) + n > n，显然，T(n) = Omega(n).

下面用数学归纳法证明T(n) = O(n)

假设T(n) <= cn，所以其中c是一个常数。

所以T(n) <= c*n/2 + c*n/4 + c*n/8 + n = (7c/8+1)n 我们只需让(7c/8+1)n <= cn，显然我们可以找到一个正常数c使该式成立。所以T(n) = O(n)。 综上，T(n) = Theta(n)。 上面的证明是没有问题了，但是可能有朋友要问，凭什么你一开始就guess T(n) = Theta(n) 呢？没错，make a good guess 是这种方法的关键，下面就简单的说一下make this guess的intuition。

首先，我们可以简单的画出下面这棵树。

6、求T(n)?2T(?n/2??17)?n的上界。【见文档】 我们推测T(n)=O(nlog n)，即推测存在正的常数C和自然数n0，使得当n≥n0时有：T(n)≤Cnlog

2

n (6.2)事实上，取n0=2=4，并取

那么，当n0≤n≤2n0时，(6.2)成立。今归纳假设当

k-1kkk+1

2n0≤n≤2n0 ，k≥1时，(1.1.16)成立。那么，当2n0≤n≤2n0时，我们有：

即(6.2)仍然成立，于是对所有n≥n0，(6.2)成立。可见我们的推测是正确的。因而得出结论：递归方程(6.1)的解的渐近阶为O(nlogn)。 当n充分大时

与相差无几。因此可以推测(6.3)与(6.1)有类似的上界

T(n)=O(nlogn)。进一步，数学归纳将证明此推测是正确的。

7、确定T(n)?9T(n/3)?n的渐近界。【见文档】

解：T(n)=aT(n/b)+f(n) (6.17)

1. 对照(6.17)，我们有a=9，b=3， f(n)=n，

有

，取，便

，有相关定理知根据f(n)，有T(n)的渐近估计式第一类情况

的公式，即：若对于某常数ε>0，有则

即T(n)=θ(n2)。

，

8、设p(x)?a0?a1x?...?adx是一个d次多项式。假设已有一个算法能在O(i)时间内计

d算一个i次多项式与一个一次多项式的乘积，以及一个算法能在O(ilogi)时间内计算两个i次多项式的乘积。对于任意给定的d个整数n1,n2,...,nd，用分治法设计一个有效算法，计算出满足P(n1)?p(n2)?...?p(nd)且最高次项系数为1的d次多项式P(x),并分析算法的效率。

9、设计一个O(n2)的时间算法，找出由n个数组成的序列的最长单调递增子序列。

10、设计一个在O（n）时间内计算p(x)?a0?a1x?...?adx的算法。

n11、数组A[1..n]中存放正整数和负整数，设计一个在O(n)时间内将所有负整数放置所有正整数之前的算法。

12、掌握用动态规划解0-1背包问题。【见文档】

13、掌握用贪心算法（prim算法）无向连通图的最小生成树。 14、掌握回溯法解0-1背包问题的解空间树[见文档] 15、掌握单纯形算法解线性规划问题[见文档8章] 16、掌握顶点覆盖问题的近似算法【9.4.2 】

无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’?V，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。

【 Cset用来存储顶点覆盖中的各顶点。初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边。即e1为空。

】

VertexSet approxVertexCover ( Graph g ) { cset=空集； e1=g.e；

while (e1 != 空集) {

从e1中任取一条边(u,v)； cset=cset∪{u,v}；

从e1中删去与u和v相关联的所有边； }

return c }

算法approxVertexCover的性能比为2 图(a)～(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。(f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。 性能分析：若用A,B分别来计算算法循环中选取的边的集合和点的集合，由算法的构造克制A中任何两条边没有公共断点且B中的点也互不关联，因为算法选了一条边，并在将其断点加入顶点覆盖集C后，就将E1中与该边关联的所有边从E1中删去，对于每次选择的点也是同样处理，故算法终止时有|C|=2A+B，而图G的最小顶点覆盖C’，则|C’|≥|A|+|B 由此可得，|C|≥2|C'|-|B ,与原算法的|C|≥2|C'|,相比，当|B远远大于|A|时，此算法比原算法显示了更大的优越性。

17、什么是P类和NP类问题

P问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。 我们常见到的一些信息奥赛的题目都是P问题。

NP类问题：首先NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题，即可以在多项式的时间里猜出一个解的问题，像Hamilton回路问题。所有的P问题都是NP问题，即能用多项式解决一个问题，必然能用多项式验证一个问题的解。 递归方程解的渐近阶的求法

1. 代入法 这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这

一推测的正确性。那么，显式解的渐近阶即为所求。

2. 迭代法 这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，

然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。

3. 套用公式法 这个方法针对形如：T (n)=aT (n / b)+f (n) 的递归方程，给出三种情况

下方程解的渐近阶的三个相应估计公式供套用。

4. 差分方程法 有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问

题)的方法来解递归方程。然后对得到的解作渐近阶的估计。 母函数法 这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数， 例如，我们要估计T(n)的上界，T(n)满足递归方程：

其中是地板(floors)函数的记号，表示不大于n的最大整数。

我们推测T(n)=O(nlog n)，即推测存在正的常数C和自然数n0，使得当n≥n0时有：

T(n)≤Cnlog n (6.2)

事实上，取n0=2=4，并取

2

那么，当n0≤n≤2n0时，(6.2)成立。今归纳假设当2n0≤n≤2n0 ，k≥1时，(1.1.16)成

kk+1

立。那么，当2n0≤n≤2n0时，我们有：

k-1

k

即(6.2)仍然成立，于是对所有n≥n0，(6.2)成立。可见我们的推测是正确的。因而得出结论：递归方程(6.1)的解的渐近阶为O(nlogn)。

这个方法的局限性在于它只适合容易推测出答案的递归方程或善于进行推测的高手。推测递归方程的正确解，没有一般的方法，得靠经验的积累和洞察力。我们在这里提三点建议： (1) 如果一个递归方程类似于你从前见过的已知其解的方程，那么推测它有类似的解是合理的。作为例子，考虑递归方程：

右边项的变元中加了一个数17，使得方程看起来难于推测。但是它在形式上与(6.1)很类似。实际上，当n充分大时

与

相差无几。因此可以推测(6.3)与(6.1)有类似的上界T(n)=O(nlogn)。进一步，数学归纳将证明此推测是正确的。

(2)从较宽松的界开始推测，逐步逼近精确界。比如对于递归方程(6.1)，要估计其解的渐近下界。由于明显地有T(n)≥n，我们可以从推测T(n)=Ω(n)开始，发现太松后，把推测的阶往上提，就可以得到T(n)=Ω(nlog n)的精确估计。

(3)作变元的替换有时会使一个末知其解的递归方程变成类似于你曾见过的已知其解的方程，从而使得只要将变换后的方程的正确解的变元作逆变换，便可得到所需要的解。例如考虑递归方程：

看起来很复杂，因为右端变元中带根号。但是，如果作变元替换m=logn，即令n=2，将其代入(6.4)，则(6.4)变成：

m

把m限制在正偶数集上，则(6.5)又可改写为：

T(2m)=2T(2m/2)+m

若令S(m)=T(2)，则S(m)满足的递归方程：

mS(m)=2S(m/2)+m ，

与(6.1)类似，因而有：

S(m)=O(m1og m)，

进而得到T(n)=T(2)=S(m)=O(m1ogm)=O(lognloglogn) (6.6)

上面的论证只能表明：当(充分大的)n是2的正偶次幂或换句话说是4的正整数次幂时(6.6)才成立。进一步的分析表明(6.6)对所有充分大的正整数n都成立，从而，递归方程(6.4)解的渐近阶得到估计。

在使用代入法时，有三点要提醒：

(1)记号O不能滥用。比如，在估计(6.1)解的上界时，有人可能会推测T(n)=O(n)，即对于充分大的n，有T(n)≤Cn ，其中C是确定的正的常数。他进一步运用数学归纳法，推出：

m

从而认为推测T(n)=O(n)是正确的。实际上，这个推测是错误的，原因是他滥用了记号O ，错误地把(C+l)n与Cn等同起来。

(2)当对递归方程解的渐近阶的推测无可非议，但用数学归纳法去论证又通不过时，不妨在原有推测的基础上减去一个低阶项再试试。作为一个例子，考虑递归方程

其中是天花板(floors)函数的记号。我们推测解的渐近上界为O(n)。我们要设法证明对

于适当选择的正常数C和自然数n0，当n≥n0时有T(n)≤Cn。把我们的推测代入递归方程，得到：

我们不能由此推断T(n)≤Cn，归纳法碰到障碍。原因在于(6.8)的右端比Cn多出一个低阶常量。为了抵消这一低阶量，我们可在原推测中减去一个待定的低阶量b，即修改原来的推测为T(n)≤Cn-b 。现在将它代人(6.7)，得到：

只要b≥1，新的推测在归纳法中将得到通过。

(3)因为我们要估计的是递归方程解的渐近阶，所以不必要求所作的推测对递归方程的初始条件（如T(0)、T(1)）成立，而只要对T(n)成立，其中n充分大。比如，我们推测(6.1)的解T(n)≤Cnlogn，而且已被证明是正确的，但是当n=l时，这个推测却不成立，因为(Cnlogn)|n=1=0而T(l)>0。

递归方程组解的渐进阶的求法——迭代法

用这个方法估计递归方程解的渐近阶不要求推测解的渐近表达式，但要求较多的代数运算。方法的思想是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。 作为一个例子，考虑递归方程：

接连迭代二次可将右端项展开为：

由于对地板函数有恒等式：

(6.10)式可化简为：

这仍然是一个递归方程，右端项还应该继续展开。容易看出，迭代 i 次后，将有

（6.11）

而且当

时，(6.11)不再是递归方程。这时：

(6.13)

又因为[a]≤a，由(6.13)可得：

而由(6.12)，知i≤log4n ，从而

，

代人(6.14)得：

即方程(6.9)的解 T(n)=O(n)。

从这个例子可见迭代法导致繁杂的代数运算。但认真观察一下，要点在于确定达到初始条件的迭代次数和抓住每次迭代产生出来的\自由项\与T无关的项)遵循的规律。顺便指出，迭代法的前几步迭代的结果常常能启发我们给出递归方程解的渐近阶的正确推测。这时若换用代入法，将可免去上述繁杂的代数运算。

图6-1 与方程(6.15)相应的递归树

为了使迭代法的步骤直观简明、图表化，我们引入递归树。靠着递归树，人们可以很快地得到递归方程解的渐近阶。它对描述分治算法的递归方程特别有效。我们以递归方程

T(n)=2T(n/2)+n2 (6.15)

为例加以说明。图6-1展示出(6.15)在迭代过程中递归树的演变。为了方便，我们假设n恰好是2的幂。在这里，递归树是一棵二叉树，因为(6.15)右端的递归项2T(n/2)可看成T(n/2)+T(n/2)。图6-1(a)表示T(n)集中在递归树的根处，(b)表示T(n)已按(6.15)展开。

2

也就是将组成它的自由项n留在原处，而将2个递归项T(n/2)分别摊给它的2个儿子结点。(c)表示迭代被执行一次。图6-1(d)展示出迭代的最终结果。

图6-1中的每一棵递归树的所有结点的值之和都等于T(n)。特别，已不含递归项的递归树(d)中所有结点的值之和亦然。我们的目的是估计这个和T(n)。我们看到有一个表格化的办法：先按横向求出每层结点的值之和，并记录在各相应层右端顶格处，然后从根到叶逐层地

2

将顶格处的结果加起来便是我们要求的结果。照此，我们得到(6.15)解的渐近阶为θ(n)。 再举一个例子。递归方程：

T(n)= T(n/3)+ T(2n/3)+n (6.16)

的迭代过程相应的递归树如图6-2所示。其中，为了简明，再一次略去地板函数和天花板函数。

图6-2迭代法解(6.16)的递归树

当我们累计递归树各层的值时，得到每一层的和都等于n，从根到叶的最长路径是

设最长路径的长度为k，则应该有

，

得

，

于是

即T(n)=O(nlogn) 。

以上两个例子表明，借助于递归树，迭代法变得十分简单易行。 递归方程组解的渐进阶的求法——套用公式法

这个方法为估计形如：

T(n)=aT(n/b)+f(n) (6.17)

的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的a≥1和b≥1是常数，f (n)是一个确定的正函数。

(6.17)是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程(6.17)。 这个方法依据的是如下的定理：设a≥1和b≥1是常数f (n)是定义在非负整数上的一个确定的非负函数。又设T(n)也是定义在非负整数上的一个非负函数，且满足递归方程(6.17)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三类情况下，我们有T(n)的渐近估计式：

1. 若对于某常数ε>0，有

，

则

；

2. 若

，

则

；

3. 若对其常数ε>0，有

且对于某常数c>1和所有充分大的正整数n有af(n/b)≤cf(n)，则T(n)=θ(f(n))。

这个方法为估计形如：

T(n)=aT(n/b)+f(n) (6.17)

的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的a≥1和b≥1是常数，f (n)是一个确定的正函数。

(6.17)是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程(6.17)。 这个方法依据的是如下的定理：设a≥1和b≥1是常数f (n)是定义在非负整数上的一个确定的非负函数。又设T(n)也是定义在非负整数上的一个非负函数，且满足递归方程(6.17)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三类情况下，我们有T(n)的渐近估计式：

1. 若对于某常数ε>0，有

，

则

；

2. 若

，

则

；

3. 若对其常数ε>0，有

且对于某常数c>1和所有充分大的正整数n有af(n/b)≤cf(n)，则T(n)=θ(f(n))。

本文来源：https://www.bwwdw.com/article/lk1d.html