數(shù)算-第7-9章書面作業(yè)解答

7.1

求證：只要適當(dāng)?shù)嘏帕许旤c(diǎn)的次序，就能使有向無環(huán)圖的鄰接矩陣中主對(duì)角線以下的元素全部為0。證明：任意n個(gè)結(jié)點(diǎn)的有向無環(huán)圖都可以得到一個(gè)拓?fù)湫蛄小ＴO(shè)拓?fù)湫蛄袨関0v1v2…vn-1，

來證明此時(shí)的鄰接矩陣A為上三角矩陣。證明采用反證法。假設(shè)此時(shí)的鄰接矩陣不是上三角矩陣，那么，存在下標(biāo)i和j（i>j），使得A[i][j]不等于零，即圖中存在從vi到vj的一條有向邊。由拓?fù)湫蛄械亩x可知，在任意拓?fù)湫蛄兄校瑅i的位置一定在vj之前，而在上述拓?fù)湫蛄衯0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，導(dǎo)致。7.2

給定圖G(V,E)和一個(gè)頂點(diǎn)s，現(xiàn)在要求s到所有頂點(diǎn)v

∈V的最短路徑權(quán)重δ(s,v)。當(dāng)所有邊的權(quán)重非負(fù)時(shí)，可以用Dijkstra算法求解這一問題。Dijkstra算法的步驟如下:123所有到s最短距離已知的頂點(diǎn)集合S；將到s估算距離最短的頂點(diǎn)v

∈V-S加入集合S；更新所有與v相連的頂點(diǎn)到s的估算距離；4重復(fù)步驟2、3，直到V-S=Φ。試證明下面兩個(gè)引理:12對(duì)于任意的v

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

∈S，有d*v+=δ(s,v)。其中，d[v]是算法運(yùn)行時(shí)用來記錄從s到v點(diǎn)當(dāng)前算出的最短距離的數(shù)組。（1）對(duì)于任意的v

∈V，在d[v]更新（松弛）前后，均有d*v+≥δ(s,v)。d[v]表示v到s的一條可行路徑的距離δ(s,v)表示v到s之間的最短距離可行解與最優(yōu)解d*v+

≥

δ(s,

v)（2）對(duì)于任意的v

∈S，有d*v+=δ(s,v)反證法如果d*v+>δ(s,v)，則存在另一條s到v的路徑長度為δ(s,v)。設(shè)這條路徑上v的前一個(gè)節(jié)點(diǎn)為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請(qǐng)完成以下給出算法的正確性證明；并且求出其時(shí)間復(fù)雜度（選做，本題要用到主定理求解遞歸方12程）。（1）給出算法的正確性證明定義(j-i+1)=k使用歸納法：k=2時(shí)顯然成立。假設(shè)對(duì)k≤2n/3都能正確排序。由假設(shè)，第一個(gè)調(diào)用sort(A,i,

j-k)正確地A*1,…,2n/3+進(jìn)行了排序，使得

A*1,…,n/3+小于A*(n+1)/3,…,2n/3+;同理，第二個(gè)調(diào)用對(duì)A*(n+1)/3,…,n+進(jìn)行了排序，使得最大的n/3個(gè)元素拍到了正確的位置。最后一個(gè)調(diào)用，使得剩下的2n/3個(gè)元素正確的進(jìn)行了排序。（2）并且求出其時(shí)間復(fù)雜度（選做，本題要用到主定理求解遞歸方程）T

n =

3T2n3+

O

1算法導(dǎo)論，主定理T

n=

O(????????3

??????1.5)情況下的時(shí)間8.2

快速排序的時(shí)間復(fù)雜度分析1請(qǐng)描述快速排序

情況，寫出復(fù)雜度遞推關(guān)系并求解。2最優(yōu)情況是每次都能夠平分?jǐn)?shù)組，如果每次劃分的結(jié)果總是1/10:9/10則時(shí)間復(fù)雜度如何？3定義一次平分的劃分為一次“幸運(yùn)的劃分”，而一次劃分如果有一邊為空則是“不幸的劃分”。如果假設(shè)劃分的過程總是幸運(yùn)和不幸交替的，請(qǐng)用任意方法計(jì)算時(shí)間復(fù)雜度。情況下的（1）請(qǐng)描述快速排序

情況，寫出時(shí)間復(fù)雜度遞推關(guān)系并求解。

的情況是每一次選取的軸值都是第一個(gè)或最后一個(gè)元素，則要進(jìn)行n-1個(gè)元素的排序。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）最優(yōu)情況是每次都能夠平分?jǐn)?shù)組，如果每次劃分的結(jié)果總是1/10:9/10則時(shí)間復(fù)雜度如何？T(n)

=

T(9n/10)

+

T(n/10)+cn則遞歸樹的最大深度為log10/9

??每一層的排序代價(jià)不大于cn所以T(n)=O(nlog10/9

??)=O(nlogn)即時(shí)間復(fù)雜度仍為O(nlogn)。（3）定義一次平分的劃分為一次“幸運(yùn)的劃分”，而一次

劃分如果有一邊為空則是“不幸的劃分”。如果假設(shè)劃分的

過程總是幸運(yùn)和不幸交替的，請(qǐng)用任意方法計(jì)算時(shí)間復(fù)雜度。設(shè)某一次為“幸運(yùn)的劃分”，則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，這與全是“幸運(yùn)的劃分”情況下表達(dá)式類似（只是最后的

變?yōu)?/p>

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

設(shè)*??1,…,????+為字母表*a,b,…,z+上的m組字符串，并且記????為字符串????的長度。嘗試通過修改基數(shù)排序，對(duì)這些字符串按字典序排序，并且使得算法的時(shí)間復(fù)雜度為????=1O(????)（簡述思路并且給出算法時(shí)間復(fù)雜度的分析）??

+

??max

≤

??

+ ????

???=1??

?

1首先，按照字符串的長度進(jìn)行保序的桶排序，使得字符串由短到長的排列。該過程時(shí)間復(fù)雜度為

O m

+

????????

，其中????????

=

max

????

。注意到：??

??=

O(

????)??=1然后,進(jìn)行????????次桶排序。第i次排序只對(duì)長度大于等于????????

?i+1的字符串的第????????

?i+1位進(jìn)行桶排序。假設(shè)長大于等于??的字符串?dāng)?shù)目為??≥??。則排序的時(shí)間代價(jià)為O ??≥??

+

26??????????=1=

O(????=1????)因而總的排序時(shí)間復(fù)雜度為O(????=1????)8.4假設(shè)數(shù)組A,1,…

,

n-中的各元素獨(dú)立同分布，給定非嚴(yán)格單調(diào)遞增函數(shù)H，將數(shù)組A,1,

…

,

n-的元素等概率地

為0到m-1（m≤

n）的m個(gè)整數(shù)。這等價(jià)于將數(shù)組A劃分為

m個(gè)桶，并且A,i-落入各個(gè)桶的概率相等，即1/m。然后分別對(duì)各個(gè)桶進(jìn)行

排序，最后按順序掃描各個(gè)桶，將數(shù)組A,1,

…

,

n-遞增輸出。假設(shè)

操作的時(shí)間復(fù)雜度均為O

1

。1證明算法的正確性2這個(gè)算法的最好、和平均時(shí)間復(fù)雜度是多少？（1）證明算法的正確性因?yàn)楹瘮?shù)H是單調(diào)不減的，保證了序號(hào)較大的桶中的元素一定大于等于序號(hào)較小的桶的元素。只要分別對(duì)各個(gè)桶進(jìn)行排序，即可保證最終輸出的正確性。和平均時(shí)間復(fù)雜（2）這個(gè)算法的最好、度是多少？最好情況:每個(gè)桶已經(jīng)排好序，則顯然復(fù)雜度為O(n)

情況:所有元素都

到一個(gè)桶中，則

排序的代價(jià)為O(n^2)平均情況:每個(gè)桶的大小為O(??

??),因而每個(gè)桶的插和查找桶的時(shí)間入排序復(fù)雜度為O(??2

??2)。而

為O(n),輸出所有元素的時(shí)間為O(n)因而平均時(shí)間復(fù)雜度為：O(??

+

??2

??)9.1

敗者樹和勝者樹是兩種完全不同的數(shù)據(jù)結(jié)構(gòu)。

舉例說明為什么敗者樹的 外存次數(shù)要比勝者樹少？敗者樹和什么數(shù)據(jù)結(jié)構(gòu)比較類似？你能否從數(shù)據(jù)結(jié)構(gòu)中信息量的角度來分析為什么敗者樹優(yōu)于勝者樹？1葉子節(jié)點(diǎn)都在外存，

外存次數(shù)實(shí)際沒有差別。敗者樹的重建是新值直接和父節(jié)點(diǎn)比較，雖然也要經(jīng)歷

O（h）（h--樹高）時(shí)間，但不需要計(jì)算兄弟節(jié)點(diǎn)的索引，直接更新父節(jié)點(diǎn)就行，而勝者樹的重建是新值和兄弟節(jié)點(diǎn)比較，要更新父節(jié)點(diǎn)不但要計(jì)算父節(jié)點(diǎn)的索引還要計(jì)算兄弟節(jié)點(diǎn)的索引。2類似于堆。完全二叉樹，頂部元素最?。ɑ蜃畲螅琌(logn)時(shí)間重構(gòu)。3敗者樹中對(duì)每個(gè)葉結(jié)點(diǎn)索引點(diǎn)都保存了一次，而勝者樹中勝者被多次保存，敗者并未保存。即同樣空間下，敗者樹保存的信息

，所以敗者樹結(jié)點(diǎn)的信息利用率較高。9.2設(shè)有11個(gè)長度(即包含記錄的個(gè)數(shù))不同的初始?xì)w并段，它們所包含的記錄個(gè)數(shù)分別為25，40，16，38，77，64，53，88，9，48，98。試根據(jù)它們做