中科大算法導(dǎo)論第一,二次和第四次作業(yè)答案

第一次作業(yè)2.2-3再次考慮線性查找問(wèn)題（見練習(xí)2.1-3）。在平均情況下，需要檢查輸入序列中的多少個(gè)元素？假定待查找的元素是數(shù)組中任何一個(gè)元素的可能性是相等的。在最壞情況下有怎樣呢？用Θ形式表示的話，線性查找的平均情況和最壞情況運(yùn)行時(shí)間怎樣？對(duì)你的答案加以說(shuō)明。線性查找問(wèn)題輸入：一列數(shù)A=<a1,a2,…,an>和一個(gè)值v。輸出：下標(biāo)i，使得v=A[i]，或者當(dāng)v不在A中出現(xiàn)時(shí)為NIL。平均情況下需要查找(1+2+…+n)/n=(n+1)/2最壞情況下即最后一個(gè)元素為待查找元素，需要查找n個(gè)。故平均情況和最壞情況的運(yùn)行時(shí)間都為Θ(n)。2.3-2改寫MERGE過(guò)程，使之不使用哨兵元素，而是在一旦數(shù)組L或R中的所有元素都被復(fù)制回?cái)?shù)組A后，就立即停止，再將另一個(gè)數(shù)組中余下的元素復(fù)制回?cái)?shù)組A中。MERGE(A,p,q,r)n1←q-p+1n2←r-qcreatearraysL[1..n1]andR[1..n2]fori←1ton1doL[i]←A[p+i-1]forj←1ton2doR[j]←A[q+j]i←1j←1k←pwhile((i<=n1)and(j<=n2))doifL[i]<=R[j]doA[k]=L[i]i++elsedoA[k]=R[j]j++k++while(i<=n1)doA[k++]=L[i++]while(j<=n2)doA[k++]=R[j++]3.2-3證明等式lg(n!)=Θ(nlgn)。并證明等式n!=ω(2n)和n!=o(nn)。第二次作業(yè)3.2-4函數(shù)?lgn?!是否多項(xiàng)式有界？函數(shù)?lglgn?!呢4.1-2證明這個(gè)遞歸的解也是Ω(nlgn)。得到解為Θ(nlgn)。4.1-4證明合并排序算法的“準(zhǔn)確”遞歸式(4.2)的解為Θ(nlgn)7.1-2當(dāng)數(shù)組A[p..r]中的元素均相同時(shí)，PARTITION返回的q值是什么？修改PARTITION，使得當(dāng)數(shù)組A[p..r]中所有元素的值相同時(shí)，q的值是r.

一種方法：記一個(gè)cnt碰上一樣的數(shù)的時(shí)候cnt＋＋對(duì)全部相同這種情況cnt=(r-p+1)進(jìn)行處理直接返回(p+r)/2。

或者修改PARTITION(A,p,r)，增加對(duì)A[i]==x時(shí)的處理。對(duì)于A[i]==x的數(shù)據(jù)，一半放在x左邊，一半放在x右邊通過(guò)設(shè)置一個(gè)flag初始為1當(dāng)flag>0時(shí)才進(jìn)行交換交換flag=-flag第四次作業(yè)intPartition(intA[],intp,intr){intx=A[r],i=p-1;intflag=1;for(intj=p;j<r-1;j++){if(x>=A[i]&&flag>0)//x=A[i]時(shí)，flag大于0和小于0的數(shù)量約為一半，{swap(A[i],A[j]);}if(x==A[i]){flag=-flag;//這樣就能讓i++次數(shù)減半。}}swap(A[i+1],A[r]);returni+1}7.2-3證明：當(dāng)數(shù)組A包含不同的元素、且按降序排序時(shí)，QUICKSORT的運(yùn)行時(shí)間為Θ(n2)。證明：數(shù)組元素各不相同，且按降序排列時(shí)，每次遞歸調(diào)用都會(huì)產(chǎn)生一個(gè)元素?cái)?shù)目為n-1的分塊和一個(gè)1的分塊。 故有T(n)=T(n-1)+Θ(n) 有T(n)=T(n-1)+cn+d =T(n-2)+cn+c(n-1)+2d =T(n-3)+cn+c(n-1)+c(n-2)+3d =... =T(1)+cn+c(n-1)+c(n-2)+...+c(1)+nd =T(1)+cn(n+1)/2+nd =Θ(n2)7.4-3證明：在q=0,1,...n-1區(qū)間上，當(dāng)q=0或q=n-1時(shí),q2+(n-q-1)2取得最大值。求導(dǎo)，取極值。或者進(jìn)行變換8.2-4在O(1)的時(shí)間內(nèi)，回答出輸入的整數(shù)中有多少個(gè)落在區(qū)間[a...b]內(nèi)。給出的算法的預(yù)處理時(shí)間為O(n+k)利用計(jì)數(shù)排序，由于在計(jì)數(shù)排序中有一個(gè)存儲(chǔ)數(shù)值個(gè)數(shù)的臨時(shí)存儲(chǔ)區(qū)C[0...k]，利用這個(gè)數(shù)組即可[a..b]區(qū)間整數(shù)個(gè)數(shù)為C[b]-C[a-1]題目已經(jīng)提示運(yùn)用桶排序，主要是正確設(shè)置桶點(diǎn)均勻分布，則每個(gè)桶的尺寸應(yīng)相等，即每個(gè)桶在圓中所占據(jù)的面積相等。把圓分為n個(gè)部分，第一個(gè)部分是以原點(diǎn)為圓心的圓，其他部分是以原點(diǎn)為圓心的圓環(huán)。單位圓的面積是π1^2=π。那么我們選擇一系列的距離d0,d1,d2,...,dn滿足d0=0,π*d1^2=π/(n),π*d2^2=2*π/(n),π*d3^2=3*π/(n),...,π*dn^2=π，得到，[d0,d1,d2,...,dn]=[0,sqrt(1/n),sqrt(2/n),...,1]這樣相當(dāng)于每個(gè)di到di+1所占的面積都是相同的，也即每個(gè)左邊點(diǎn)會(huì)均勻的落入這些區(qū)間中。所n個(gè)桶為[d0,d1],[d1,d2],...,[dn-1,dn]9.1-1證明：在最壞情況下，利用n+ceil(lgn)-2次比較，即可得到n個(gè)元素中的第2小元素。（提示：同時(shí)找最小元素）先兩兩比較，較小的組成新的數(shù)組再兩兩比較，不斷如此，從而形成一個(gè)倒立的樹，終于找出最小的元素，由于最上一層是n/2次比較，這又能