MergeSortLQuicksort改進(jìn)插入排序算法(第三章pptNo.6)，在插入元素a(i)時(shí)使用二分查找代替順序查找，將這個(gè)算法記做ModInsertSort，估計(jì)算法在最壞情況下的時(shí)間復(fù)雜度。ModInsertSort(A[1..n]) fori:=2tondox:=A[i]k:=BinarySearch(A[1..i-1],x)//在A[1..i-1]查找x應(yīng)該插入的位置kA[k]:=x復(fù)雜度分析：外for循環(huán)n-1次，在i-1規(guī)模的數(shù)組中二分比較次數(shù)為<=log(i-1)+1，因此總比較次數(shù)為：（但移動(dòng)次數(shù)沒(méi)節(jié)省）設(shè)A是n個(gè)非0實(shí)數(shù)構(gòu)成的數(shù)組，設(shè)計(jì)一個(gè)算法重新排列數(shù)組中的數(shù)，使得負(fù)數(shù)都排在正數(shù)前面，要求算法復(fù)雜度為O(n)。類似快速排序的劃分過(guò)程。從后向前把每個(gè)數(shù)與0比較，找到第一個(gè)負(fù)數(shù)A[p];從前向后把每個(gè)數(shù)與0比較，找到第一個(gè)正數(shù)A[q]，如果P>q，則將A[p]與A[q]交換。交換后如果p-q=1，算法停止，否則繼續(xù)這個(gè)過(guò)程。Hanoi塔問(wèn)題。圖中有A、B、C三根柱子，在A柱上放著n個(gè)圓盤(pán)，其中小圓盤(pán)放在大圓盤(pán)的上邊。從A柱將這些圓盤(pán)移到C柱上去，在移動(dòng)和放置時(shí)允許使用B柱，但不能把大盤(pán)放到小盤(pán)的下面。設(shè)計(jì)算法解決此問(wèn)題，分析算法復(fù)雜度。算法復(fù)雜度：T(n)=2T(n-1)+1=4T(n-2)+2+1=2n-1+2n-2+…+1=2n-1給定含有n個(gè)不同數(shù)的數(shù)組L={x1,x2,…,xn}，如果L中存在xi，使得x1<x2<…<xi-1<xi>xi+1>…>xn，則稱L是單峰的，并稱xi是L的峰頂。假設(shè)L是單峰的，設(shè)計(jì)一個(gè)優(yōu)于O(n)的算法找到L的峰頂。因?yàn)長(zhǎng)中存在峰頂元素，因此|L|>=3。使用二分查找算法。如元素?cái)?shù)等于3，則L[2]是峰頂元素，當(dāng)元素?cái)?shù)n>3時(shí)，令k=n/2，比較L[k]與它左邊和右邊相鄰的項(xiàng)，如果L[k]>L[k-1]且L[k]>L[k+1]則L[k]為峰頂元素；否則，如果L[k-1]>L[k]>L[k+1]，則繼續(xù)搜索L[1..k-1]，如果L[k-1]<L[k]<L[k+1]則繼續(xù)搜索L[k+1..n]的范圍。每比較兩次，搜索范圍減半，直到元素?cái)?shù)小于3停止遞歸調(diào)用。時(shí)間復(fù)雜度T(n)=T(n/2)+2，根據(jù)主定理，T(n)=O(logn)。設(shè)A是n個(gè)不同的排好序的數(shù)組，給定數(shù)L和U，L<U，設(shè)計(jì)一個(gè)優(yōu)于O(n)的算法，找到A中滿足L<x<U的所有數(shù)x。在A中使用二分查找算法找L，如果L=A[i]，找到L的位置i，然后把i加1;如果L不在A中，那么找到大于L的最小數(shù)的位置i。類似地，找到U的位置A[j]，j=j+1，或小于U的最大數(shù)A[j]。輸出A中i到j(luò)的全體數(shù)。.設(shè)A={a1,a2,…,an},B={b1,b2,…,bm}是整數(shù)集合，其中m=O(logn)，設(shè)計(jì)一個(gè)優(yōu)于O(nm)的算法法找出集合C=A∩B。（即找出一個(gè)優(yōu)于nlogn的方法）所得方法為nlogm設(shè)S是n個(gè)不等的正整數(shù)的集合，n為偶數(shù)，給出一個(gè)算法將S劃分為子集S1和S2，使得|S1|=|S2|且達(dá)到最大，即兩個(gè)子集元素之和的差達(dá)到最大。(要求：T(n)=O(n))。規(guī)定S的中位數(shù)x是從小到大排序的第n/2個(gè)數(shù)，用x劃分S，比x小的整數(shù)屬于S1，x本身也放到S1，其余的放到S2，由于n是偶數(shù)，|S1|=|S2|，易見(jiàn)這樣的集合滿足要求。算法復(fù)雜度：找中位數(shù)和劃分都是O(n)，所以T(n)=O(n)。補(bǔ)充算法實(shí)現(xiàn)考慮第三章PPTNO.17Select(A,k)算法：（1）如果初始元素分組r=3，算法的時(shí)間復(fù)雜度如何？(2)如果初始元素分組r=7，算法的時(shí)間復(fù)雜度如何？(1)r=3，不妨設(shè)n是3的倍數(shù)。每組至少2個(gè)元素不大于u，A中至少2*n/3/2>=n/3=n/3個(gè)不大于v，即A中至多n-n/3<=n-n/3=2n/3個(gè)元素大于v。同理，至多有2n/3個(gè)元素小于v。即子問(wèn)題的規(guī)模小于2n/3。所以，T(n)=T(n/3)+T(2n/3)+O(n)，得T(n)=O(nlogn)。與直接排序方法的復(fù)雜度一樣。(2)問(wèn)題變?yōu)?*n/7/2>=2n/7，子問(wèn)題規(guī)模小于n-2n/7=5n/7（不妨設(shè)n是7的倍數(shù)）T(n)=T(n/7)+T(5n/7)+O(n)=n(1+6/7+(6/7)2+…+(6/7)k)+O(n)=O(n)11.對(duì)玻璃瓶做強(qiáng)度試驗(yàn)，設(shè)地面高度為0，從0向上有n個(gè)高度，記為1,2,…,n，其中任何兩個(gè)高度之間的距離都相等。如果一個(gè)玻璃瓶從高度i落到地上沒(méi)有摔碎，但從高度i+1落到地上摔碎了，那么就將玻璃瓶的強(qiáng)度記為i。(1)假設(shè)每種玻璃瓶只有1個(gè)測(cè)試樣品，設(shè)計(jì)算法來(lái)測(cè)試出每種玻璃瓶的強(qiáng)度。以測(cè)試次數(shù)作為算法的時(shí)間復(fù)雜度量度，估計(jì)算法的復(fù)雜度。(2)假設(shè)每種玻璃瓶有足夠多的相同的測(cè)試樣品，設(shè)計(jì)算法使用最少的測(cè)試次數(shù)來(lái)完成測(cè)試。(3)假設(shè)每種玻璃瓶只有2個(gè)相同的測(cè)試樣品，設(shè)計(jì)次數(shù)盡可能少的算法完成測(cè)試。解：(1)只好順序從下到上測(cè)試，一次一個(gè)高度，最壞T(n)=O(n)(2)二分查找法。取n/2高度進(jìn)行第一次測(cè)試，如果瓶子沒(méi)有摔碎，則強(qiáng)度在[n/2+1,n]之間，否則在[1,n/2]之間。每次測(cè)試后可能一個(gè)瓶子的代價(jià)，測(cè)試范圍減半，最壞時(shí)間復(fù)雜度T(n)=O(logn)。(3)為簡(jiǎn)單起見(jiàn)，不妨設(shè)為整數(shù)，將高度1,2,..,n分為個(gè)組，每組高度，取第一個(gè)瓶子從下到上測(cè)試每組的最大高度，即高度,2…n，如果k-1組沒(méi)碎，k組碎了，那么玻璃瓶子的強(qiáng)度在第k組內(nèi)，于是，再經(jīng)至多次測(cè)試，就可以得到瓶子的強(qiáng)度。T(n)=O()+O()=O()(1)a=9,b=3,f(n)=n，log39=2,f(n)的階低于nlogba,符合情況1，T(n)=(nlogba)=(n2)。(2)a=5,b=2,f(n)=n2log2n=O(nlog25-ε)，方法T(n)=(nlog25)(3)a=2,b=2,f(n)=n2logn,取c=3/4則af(n/b)=2(n/2)2log(n/2)=(n2/2)(logn-1)≤(n2/2)logn≤cn2logn=cf(n)于是，符合情況3，T(n)=(n2logn)使用遞歸樹(shù)求解：T(n)=cn+3cn/4+(3/4)2cn+(3/4)3cn+…..=[1+3/4+(3/4)2+(3/4)3+…]cn=(n)例：使用迭代遞歸法求