数算-第7-9章书面作业解答

7.1

求证：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。证明：任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，

来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导致。7.2

给定图G(V,E)和一个顶点s，现在要求s到所有顶点v

∈V的最短路径权重δ(s,v)。当所有边的权重非负时，可以用Dijkstra算法求解这一问题。Dijkstra算法的步骤如下:123所有到s最短距离已知的顶点集合S；将到s估算距离最短的顶点v

∈V-S加入集合S；更新所有与v相连的顶点到s的估算距离；4重复步骤2、3，直到V-S=Φ。试证明下面两个引理:12对于任意的v

∈V，在d[v]更新（松弛）前后，均有d*v+≥δ(s,v)。对于任意的v

∈S，有d*v+=δ(s,v)。其中，d[v]是算法运行时用来记录从s到v点当前算出的最短距离的数组。（1）对于任意的v

∈V，在d[v]更新（松弛）前后，均有d*v+≥δ(s,v)。d[v]表示v到s的一条可行路径的距离δ(s,v)表示v到s之间的最短距离可行解与最优解d*v+

≥

δ(s,

v)（2）对于任意的v

∈S，有d*v+=δ(s,v)反证法如果d*v+>δ(s,v)，则存在另一条s到v的路径长度为δ(s,v)。设这条路径上v的前一个节点为u若u在S中，则d[v]<=d[u]+dis[u,v+=δ(s,v)，若u不在S中，则d[u]>=d[v]>d[u]+dis[u,v]，8.1

给定如下排序算法:sort

A,

i,

jIf

A

i>

A,j-

thenSwap(A

i

,

A,j-)If

j−

i

+

1 ≥

3thent

=

(j

−

i

+1)/3sort

A,

i,

j

−tsort(A,

i

+

t,

j)sort(A,

i,

j

−

t)Return

A请完成以下给出算法的正确性证明；并且求出其时间复杂度（选做，本题要用到主定理求解递归方12程）。（1）给出算法的正确性证明定义(j-i+1)=k使用归纳法：k=2时显然成立。假设对k≤2n/3都能正确排序。由假设，第一个调用sort(A,i,

j-k)正确地A*1,…,2n/3+进行了排序，使得

A*1,…,n/3+小于A*(n+1)/3,…,2n/3+;同理，第二个调用对A*(n+1)/3,…,n+进行了排序，使得最大的n/3个元素拍到了正确的位置。最后一个调用，使得剩下的2n/3个元素正确的进行了排序。（2）并且求出其时间复杂度（选做，本题要用到主定理求解递归方程）T

n =

3T2n3+

O

1算法导论，主定理T

n=

O(𝑛𝑙𝑜𝑔3

𝑙𝑜𝑔1.5)情况下的时间8.2

快速排序的时间复杂度分析1请描述快速排序

情况，写出复杂度递推关系并求解。2最优情况是每次都能够平分数组，如果每次划分的结果总是1/10:9/10则时间复杂度如何？3定义一次平分的划分为一次“幸运的划分”，而一次划分如果有一边为空则是“不幸的划分”。如果假设划分的过程总是幸运和不幸交替的，请用任意方法计算时间复杂度。情况下的（1）请描述快速排序

情况，写出时间复杂度递推关系并求解。

的情况是每一次选取的轴值都是第一个或最后一个元素，则要进行n-1个元素的排序。T(n)

=

T(n-1)+cnT(n-1)

=

T(n-2)+c(n-1)…T(2)

=

T(1)

+

c(2)得T(n)=c*n*(n-1)/2=Θ(n2)（2）最优情况是每次都能够平分数组，如果每次划分的结果总是1/10:9/10则时间复杂度如何？T(n)

=

T(9n/10)

+

T(n/10)+cn则递归树的最大深度为log10/9

𝑛每一层的排序代价不大于cn所以T(n)=O(nlog10/9

𝑛)=O(nlogn)即时间复杂度仍为O(nlogn)。（3）定义一次平分的划分为一次“幸运的划分”，而一次

划分如果有一边为空则是“不幸的划分”。如果假设划分的

过程总是幸运和不幸交替的，请用任意方法计算时间复杂度。设某一次为“幸运的划分”，则T(n)=2T(n/2)+cn，下一次为“不幸的划分”，T(n/2)=T(n/2-1)+cn/2，得T(n)=2T(n/2-1) ≤

2T(n/2)

+

2cn，这与全是“幸运的划分”情况下表达式类似（只是最后的

变为

）所以T(n)仍等于O(nlogn)。8.3

设*𝑠1,…,𝑠𝑚+为字母表*a,b,…,z+上的m组字符串，并且记𝑙𝑖为字符串𝑠𝑖的长度。尝试通过修改基数排序，对这些字符串按字典序排序，并且使得算法的时间复杂度为𝑚𝑖=1O(𝑙𝑖)（简述思路并且给出算法时间复杂度的分析）𝑚

+

𝑙max

≤

𝑚

+ 𝑙𝑖

−𝑖=1𝑚

−

1首先，按照字符串的长度进行保序的桶排序，使得字符串由短到长的排列。该过程时间复杂度为

O m

+

𝑙𝑚𝑎𝑥

，其中𝑙𝑚𝑎𝑥

=

max

𝑙𝑖

。注意到：𝑚

𝑚=

O(

𝑙𝑖)𝑖=1然后,进行𝑙𝑚𝑎𝑥次桶排序。第i次排序只对长度大于等于𝑙𝑚𝑎𝑥

−i+1的字符串的第𝑙𝑚𝑎𝑥

−i+1位进行桶排序。假设长大于等于𝑙的字符串数目为𝑛≥𝑙。则排序的时间代价为O 𝑛≥𝑙

+

26𝑙𝑚𝑎𝑥𝑙=1=

O(𝑚𝑖=1𝑙𝑖)因而总的排序时间复杂度为O(𝑚𝑖=1𝑙𝑖)8.4假设数组A,1,…

,

n-中的各元素独立同分布，给定非严格单调递增函数H，将数组A,1,

…

,

n-的元素等概率地

为0到m-1（m≤

n）的m个整数。这等价于将数组A划分为

m个桶，并且A,i-落入各个桶的概率相等，即1/m。然后分别对各个桶进行

排序，最后按顺序扫描各个桶，将数组A,1,

…

,

n-递增输出。假设

操作的时间复杂度均为O

1

。1证明算法的正确性2这个算法的最好、和平均时间复杂度是多少？（1）证明算法的正确性因为函数H是单调不减的，保证了序号较大的桶中的元素一定大于等于序号较小的桶的元素。只要分别对各个桶进行排序，即可保证最终输出的正确性。和平均时间复杂（2）这个算法的最好、度是多少？最好情况:每个桶已经排好序，则显然复杂度为O(n)

情况:所有元素都

到一个桶中，则

排序的代价为O(n^2)平均情况:每个桶的大小为O(𝑛

𝑚),因而每个桶的插和查找桶的时间入排序复杂度为O(𝑛2

𝑚2)。而

为O(n),输出所有元素的时间为O(n)因而平均时间复杂度为：O(𝑛

+

𝑛2

𝑚)9.1

败者树和胜者树是两种完全不同的数据结构。

举例说明为什么败者树的 外存次数要比胜者树少？败者树和什么数据结构比较类似？你能否从数据结构中信息量的角度来分析为什么败者树优于胜者树？1叶子节点都在外存，

外存次数实际没有差别。败者树的重建是新值直接和父节点比较，虽然也要经历

O（h）（h--树高）时间，但不需要计算兄弟节点的索引，直接更新父节点就行，而胜者树的重建是新值和兄弟节点比较，要更新父节点不但要计算父节点的索引还要计算兄弟节点的索引。2类似于堆。完全二叉树，顶部元素最小（或最大），O(logn)时间重构。3败者树中对每个叶结点索引点都保存了一次，而胜者树中胜者被多次保存，败者并未保存。即同样空间下，败者树保存的信息

，所以败者树结点的信息利用率较高。9.2设有11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25，40，16，38，77，64，53，88，9，48，98。试根据它们做