杭電算法分析與設(shè)計(jì)復(fù)習(xí)提綱

杭電算法設(shè)計(jì)與分析復(fù)習(xí)提綱TOC杭電算法設(shè)計(jì)與分析復(fù)習(xí)提綱1學(xué)弟學(xué)妹求送點(diǎn)財(cái)富1填空題5快速排序的隨機(jī)化版本5計(jì)數(shù)排序6學(xué)弟學(xué)妹求送點(diǎn)財(cái)富這份答案是在2014年上半年總結(jié)，紅色部分為考到的題目，老師沒有對(duì)題目做無任何修改選擇判斷蒙一下就可以了40分。簡答題5*8=40分5.2-3求骰子期望值略7.1-4應(yīng)如何修改QUICKSORT，才能使其按非增序進(jìn)行排序？在劃分子樹組時(shí)，將大于主元的元素放左邊，小于主元的元素放右邊7.2-2當(dāng)數(shù)組A的所有元素都具有相同值時(shí)，QUICKSORT的運(yùn)行時(shí)間是什么？7.2-4銀行經(jīng)常按照交易時(shí)間，來記錄有關(guān)某一賬戶的交易情況，但是，很多人喜歡按照票據(jù)號(hào)來收到其銀行對(duì)賬單。因此，如何將按交易時(shí)間排序轉(zhuǎn)換成按支票編號(hào)來排序，就成為一個(gè)對(duì)幾乎排好序的輸入進(jìn)行排序的問題。證明在這個(gè)問題上，過程INSERT_SORT的性能往往優(yōu)于過程QUIKSORT。 （引用自網(wǎng)絡(luò))對(duì)于QUIKSORT來說，輸入一個(gè)已排序的數(shù)組屬于最壞的情況，則每次區(qū)間劃分都是最大程度的不對(duì)稱。其算法運(yùn)行的遞歸時(shí)間為T(n)=T(n-1)+Θ(n)，算法時(shí)間復(fù)雜度為Θ(n^2)；而對(duì)INSERT-SORT來說，輸入一個(gè)已排序的數(shù)組卻屬于最佳的情況，算法時(shí)間復(fù)雜度為O(n)。也就是說當(dāng)輸入一個(gè)幾乎排好序的數(shù)組，快速排序趨于最壞的情況，而插入排序卻趨于最佳的情況7.3-2在過程RANDOMIZED_QUIKSORT的運(yùn)行過程中，最壞情況下對(duì)隨機(jī)排序產(chǎn)生器RANDOM調(diào)用了多少次？最佳情況下調(diào)用了多少次？以Θ記號(hào)形式個(gè)給出你的答案。 （引用自網(wǎng)絡(luò))隨機(jī)快速排序中，只要區(qū)間包含元素?cái)?shù)目大于1，則需調(diào)用RANDOMIZED-PARTITION，選取主元（pivot）進(jìn)行區(qū)間劃分，而主元的選取需調(diào)用Random。主元（pivot）一旦被選出來后，就不會(huì)在加入到后續(xù)的排序了。直白來說就是，有多少次主元（pivot）選取就有多少次隨機(jī)數(shù)生成。另一方面從算法的遞歸二叉樹樹上來看，遞歸樹二叉樹的非葉子節(jié)點(diǎn)可表示一個(gè)主元（pivot）；而葉子節(jié)點(diǎn)分為兩種，一種節(jié)點(diǎn)是包含0個(gè)元素，另一種節(jié)點(diǎn)是包含1個(gè)元素，而且該元素不是主元（pivot）。非葉子節(jié)點(diǎn)和包含1個(gè)元素的葉子節(jié)點(diǎn)的數(shù)目之和就是輸入序列的大小n。即遞歸樹的非葉子節(jié)點(diǎn)的數(shù)目就是調(diào)用RANDOM的次數(shù)。調(diào)用RANDOM次數(shù)T(RANDOM)≤n，即T(RANDOM)=O(n)。又根據(jù)二叉樹的性質(zhì)，對(duì)于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為a，而度數(shù)為2的結(jié)點(diǎn)（非葉子節(jié)點(diǎn)）總數(shù)為b，則a=b+1；對(duì)于快速排序的遞歸二叉樹中，非葉子節(jié)點(diǎn)度數(shù)均為2。假設(shè)含有0個(gè)元素的葉子節(jié)點(diǎn)數(shù)目a0（≥0），含有1個(gè)元素的葉子節(jié)點(diǎn)數(shù)目為a1，所以b=a-1≥a1-1；又b+a1=n，可得b≥n/2-1，即T(RANDOM)=Ω(n)。這里有錯(cuò)誤8.2-4請(qǐng)給出一個(gè)算法，使之對(duì)給定的介于0到k之間的n個(gè)整數(shù)進(jìn)行預(yù)處理，并能在O(1)時(shí)間內(nèi)回答出輸入的整數(shù)中有多少個(gè)落在[a...b]區(qū)間內(nèi)。你給出的算法的預(yù)處理時(shí)間為Θ(n+k)。略8.3-4說明如何在O(n)時(shí)間內(nèi)，對(duì)0~n^2-1之間的n個(gè)數(shù)進(jìn)行排序。把整數(shù)轉(zhuǎn)換為n進(jìn)制再排序，每個(gè)數(shù)有兩位，每位的取值范圍是[0..n-1]，再進(jìn)行基數(shù)排序引用自/mishifangxiangdefeng/article/details/76858398.4-2桶排序的最壞情況運(yùn)行時(shí)間是什么？如果要在保持其線性運(yùn)行時(shí)間的同時(shí)，使最壞情況時(shí)間為O(nlgn)，要對(duì)算法做什么樣的修改？當(dāng)分布不均勻時(shí)，全部元素都分到一個(gè)桶中，則O(n^2)，當(dāng)然[算法導(dǎo)論8.4-2]也可以將插入排序換成堆排序、快速排序等，這樣最壞情況就是O(nlgn)。9.1-1證明：在最壞情況下，利用n+(lgn)-2次比較，即可得到n個(gè)元素中的第2小元素。（提示：同時(shí)找最小元素）.對(duì)所有元素，兩個(gè)一組比較大小，小的一個(gè)進(jìn)入下一輪比較。一直到比較出最小的元素。此時(shí)所有比較結(jié)果構(gòu)成一棵二叉樹。比較次數(shù)為n-1。略詳情百度，懶的打了。9.2-1證明:在RANDOMIZED-SELECT中,對(duì)于長度為0的數(shù)組,不會(huì)進(jìn)行遞歸調(diào)用.從RANDOMIZED-SELECT函數(shù)知，長度為0的數(shù)組p=r，那么直接返回A[p].不做下面的隨機(jī)劃分和遞歸調(diào)用。9.3-3假定元素的值不同，說明如何才能使快速排序在最壞情況下以O(shè)(nlgn)時(shí)間運(yùn)行.以RANDOMIZED-SELECT作為選擇中值的算法9.3-7給出一個(gè)O(n)時(shí)間的算法，在給定一個(gè)有n個(gè)不同數(shù)字的集合S以及一個(gè)正整數(shù)k<=n后，它能確定出S中最接近其中位數(shù)的k個(gè)數(shù).step1：求出數(shù)組的中位數(shù)的值O(n)step2：計(jì)算數(shù)組每個(gè)數(shù)與中位數(shù)差的絕對(duì)值，存于另一個(gè)數(shù)組B中O(n)step3：求出數(shù)組B中第k小的數(shù)retO(n)step4：計(jì)算數(shù)組S中與ret差的絕對(duì)值小于ret的數(shù)并輸出O(n)其中，step4也可以通過劃分的方法找出數(shù)組S中與ret差的絕對(duì)值小于ret的數(shù)13.1-5證明:在一棵紅黑樹中,從某結(jié)點(diǎn)x到其后代葉結(jié)點(diǎn)的所有簡單路徑中,最長的一條是最短一條的至多兩倍.在一棵紅黑樹中，從某結(jié)點(diǎn)x到其后代葉結(jié)點(diǎn)的所有簡單路徑中，最長的一條是最短一條的至多兩倍。反證法：假設(shè)存在一條最長路徑長度是最短路徑長度的2倍多1，即L1=k，L2=2k+1。為保證從根節(jié)點(diǎn)到L1和L2的黑高度相同，最小黑高為k，否則L2上必然出現(xiàn)兩個(gè)紅色是父子關(guān)系。那么L2中有k個(gè)黑色，k+1個(gè)紅色，由于根節(jié)點(diǎn)必須是黑色，那么lL2中必定存在紅色的子節(jié)點(diǎn)不是黑色的情況，因此與假設(shè)矛盾，命題得證。14.1-4寫出一個(gè)遞歸過程OS-KEY-RANK(T,k)使得順序統(tǒng)計(jì)樹T和某個(gè)關(guān)鍵字k為輸入，輸出k的秩（排序）。14.1-5給定含有n個(gè)元素的順序統(tǒng)計(jì)樹中的一個(gè)元素x和一個(gè)自然數(shù)i，如何在O(lgn)的時(shí)間內(nèi)找到元素x的第i個(gè)后繼？15.2-2請(qǐng)給出一個(gè)遞歸算法MATRIX-CHAIN-MULTIPLY(A,s,i,j)，使之在給出矩陣序列<A1,A2,...,An>，和由MATRIX-CHAIN-ORDER計(jì)算出的表s，以及下標(biāo)i和j后，能得出一個(gè)最優(yōu)的矩陣鏈乘法。(初始調(diào)用為MATRIX-CHAIN-MULTIPLY(A,s,1,n))。MATRIX-CHAIN-MULTIPLY(A,s,i,j)if(j>i)x=MATRIX-CHAIN-MULTIPLY(A,s,i,s(i,j))y=MATRIX-CHAIN-MULTIPLY(A,s,s(i,j)+1,j)returnMATRIX_MULTIPLY(x,y)elsereturnAi15.3-2畫出2.3.1節(jié)的過程MERGE-SORT作用于一個(gè)包含16個(gè)元素的數(shù)組上的遞歸樹。請(qǐng)解釋在加速一個(gè)好的分治算法如MERGE-SORT方面，做備忘錄方法為什么沒有效果？沒有重疊子問題16.1-2假設(shè)不再總是選擇第一個(gè)結(jié)束的活動(dòng)，而是選擇最后一個(gè)開始、且與之前選入活動(dòng)兼容的活動(dòng)。試說明這種方式如何成為一個(gè)信心算法，并證明它能得到一個(gè)最優(yōu)解。16.2-4Midas教授從Newark開一輛車沿著80號(hào)洲際公司到Reno。他車子的油箱在滿的時(shí)候可以存放夠跑n英里的汽油，并且他的地圖標(biāo)出子在他的路途中加油站之間的距離。教授希望在路途中盡量少加油。請(qǐng)給出一個(gè)高效的方法，來幫助教授決定哪一