算法设计大作业 哈工大 王宏志

算法设计大作业

软件学院

软件2班

1093710219 周宇

一、

1.1

解

递推求解如下：

A(n) = 3A(n/2) + n 22

= 3 A(n/2)+3(n/2) + n = 33 A(n/23)+32(n/22)+3(n/2) + n ……

=3k A(n/2k)+3i(n/2i)

设 n= 2k k=log2n 有 3i(n/2i) = n3i/2i

=(3k-2k)/(3/2 - 1)=O(3k)=O(3log2n)= O(nlog23)

T(n) = nlog23 +O(nlog23)=

或根据master 定理 直接带入公式… 亦可得T(n ) = 1.2

解

递推求解如下：

B(n) = 2B(n/2) + n/ lg n 首先 根据master 定理 ==>=f(n) 其中 接近为0. 又因为n/lgn < n 。

所以B(n) =2B(n/2) + n/ lg n<2B(n/2) + n 既得 B(n)< (nlgn)

1.3 解 猜测解为H(n)=O(nlgn)，下证H(n)<=dnlgn，当d是一个合适的正值常数，有 H(n)<=d(n/2)lgn/2+d(n/4)lgn/4+d(n/6)lgn/6+d(n/12)lgn/12+n =dnlgn-d(n/2)lg2-d(n/4)lg4-d(n/6)lg6-d(n/12)lg12+n <=dnlgn

使上式成立的条件时d>1/(4lg2/3+lg3/4)

假设 1.4 解

递推求解如下：

G(n) = G(n?1) + 1/n 同1.1 可得

……

= G(1) + 1/2+……+1/n = G(1) + Ln(n)+R-1

= Ln(n)+O(1)

二、

给定两个大小分别为m和n的已经排序的序列A和B, 给出一个算法求得序列A和B的并集中第k小元素，要求时间复杂性为O(logm + log n)。

1. 取a=, b=

2. 若k<=a+b,比较A[a]和B[b]，

若A[a]>B[b],即知第k小的元素不在A的后半部，则将A去掉后半部分,令m=a,n=n。否则将B的后半部分去掉，令m=m,n=b。 3. 类比2，反面易得…

若k>a+b, 比较A[a]和B[b]。

若A[a]>B[b], 即知第k小的元素不在B的前半部分，则将去掉B的前半部分，改为寻找第k-b大的元素，否则将去掉A的后前部分，寻找第k-a大的元素。 4. 重复过程2、3直至为空。

三、 1. 证 明=

2. 判断是否=, 请证明你的结论 3. 判断是否=, 请证明你的结论…… 3.1

<=4n=O(n)

>=(1/4)*n= 所以 原式 3.2

是

证明：

令c=1, 显然

再令c=1/4，

则c*<(1/4)*<=(1/2)*=< 所以=

3.3 否

证明：

令c=4，则>4*=>=

再令c=1/4，则=(1/4)*<(1/4)* = < 即得 =

假设存在c，使得n>k时候，有>c*

c(1/)*=

矛盾，假设错误 所以=不成立。 四、

STUPIDSORT(A*0 .. n ? 1+) : if n = 2 and A[0] > A[1] swap A*0+ ? A*1+ else if n > 2 m = ?2n/3?

STUPIDSORT(A*0 ..m?1+) STUPIDSORT(A*n?m.. n-1]) STUPIDSORT(A*0..m?1+)

(1) 证明STUPIDSORT得到的结果是一个正确的排序。

(2) 如果算法中的 m = ?2n/3? 替换为 m = ?2n/3?，算法是否仍然得到正确的排序结果？

证明你的结论。

(3) 列递归方程求解算法STUPIDSORT中比较的个数。 (4) 证明在算法执行过程中swap执行了至多C次。

4.1 证明:

假设第i次所得结果为真，则A[n]可分成三份，即：较大，较小，和中间份。经过第一次STUPIDSORT(A[0,……,m-1])后。A[a3， n-m]中则为最大的一份。即A[n-m+1,……，n-1]中含有全部最大的一份，则STUPIDSORT(A[n-m,n-1])后，则A[m,n-1]中已是最大一份。所以

A[0,m-1]中含有较小和中间份。所以经过三次STUPIDSORT(A[09……m-1])后，真个数组就都排好了。因此为正确排序….

注:借鉴了同学的证明方法，觉得蛮有道理。 4.2 不正确

证明：

假如取n=7，那么第一次中m=4，假设序列为A[]={3,4,5,6,7,1,2}，那么STUPIDSORT(A[0 ..m?1])对前面的排序为3,4,5,6，STUPIDSORT(A[n?m.. n-1])对后面的排序为1,2,6,7,最后STUPIDSORT(A[0 ..m?1])排序为1,3,4,5,最后结果为1,3,4,5,2,6,7.显然不满足要求。 4.3

T(2)=1, T(n)=T(?2n/3?)+ T(?2n/3?)+ T(?2n/3?)=3 T(?2n/3?)<3T(2n/3+1) 假设T(n)<

n=2的时候显然成立

n=20的时候，递归计算可知T(20)=729<20*20*20 假设n20)

T(k)= 3 T(?2k/3?)<3T(2n/3+1)=3= 显然2/<1,并且当k>20时，显然2k/+1

所以T(n)=O() 4.4

证明： 显然，算法中能执行swap的元素是相邻的两个元素（包括一开始就相邻和算法执行过程中相邻），并且交换后不会再交换，所以相当于从n个元素中取出2个来交换，并且这两个元素取出顺序无影响，所以最多交换C次。