I题目1（排序（Sorting））现有一堆石头和一个天平，请借助天平将石头按照重量进行排序。你所能做的基本操作是通过一次称量比较两块石头的轻重（1）请设计算法完成该任务（要求给出伪代码），并分析算法在最坏情况下的渐进时间复杂度。（2）该问题本身的难度是什么？请证明你的结论I
题目1（排序（Sorting）） 现有一堆石头和一个天平，请借助天平将石头按照重量进行排 序。你所能做的基本操作是通过一次称量比较两块石头的轻重。 （1）请设计算法完成该任务（要求给出伪代码），并分析算法 在最坏情况下的渐进时间复杂度。 （2）该问题本身的难度是什么？请证明你的结论 “
1题目1（排序（Sorting））现有一堆石头和一个天平，请借助天平将石头按照重量进行排序。你所能做的基本操作是通过一次称量比较两块石头的轻重（1）请设计算法完成该任务（要求给出伪代码），并分析算法在最坏情况下的渐进时间复杂度。（2）该问题本身的难度是什么？请证明你的结论I
题目1（排序（Sorting）） 现有一堆石头和一个天平，请借助天平将石头按照重量进行排 序。你所能做的基本操作是通过一次称量比较两块石头的轻重。 （1）请设计算法完成该任务（要求给出伪代码），并分析算法 在最坏情况下的渐进时间复杂度。 （2）该问题本身的难度是什么？请证明你的结论 “
本人的算法导论的Merge-Sort(A,a,b,r,B):MERGE-SORT(A, P,r)1.Ifa-b==0orb-a==1:1ifp<r21.Returnq=[(p+r)/2]32.Elseif b-a==2:MERGE-SORT(A,P,9)4MERGE-SORT(A,g+1,r)1. If A[a] > A[6-1]:5MERGE(A, P,q,r)1. Swap A[a] and A[6 - 1]2.ReturnMERGE(A, P.q,r)1ni=q-p+l3.Else:2n2=r-q1.Merge-Sort(A,a,L」+1,r,B)3let L[1..n + 1] and R[1..n2 + 1] be new arrays42. Merge-Sort(A,[ath] +1,b,r,B)fori=ltoni5L=Ap+i-!]3. =a,y=[] +16forj=lto n274. For(i=a;i<b;i++):R] =A[q+]8L[n+ 1] = 001. If A[] ≤A[] and <[] +19R[n2+ 1] =001. B[] =A[],a ++10i=l11j=2.Else:12fork=ptor1. B[] = A[y], y + +13if L[] ≤ R[i]14A[K] =- L[i]5.For(i=a;i<b;i++):15i=i+l1. A[] = B[]16else A[K] = R[i]17j=j+l
算法导论的MERGE-SORT(A, P,r)第一问：1ifp<r因为对于一个长度为n的数2q=L(p+r)/2组，最坏的情况是在最基3MERGE-SORT(A,P,9)础的情况，也就是a=2时4MERGE-SORT(A,9+1,r)要交换，且第一个For循环5MERGE(A, P,q,r)要判断两次，而For循环那里所话的时间为○(r），即MERGE(A,P.q,r)为长度，所以有式子1ni=q-p+1T(n)= 2T ()+ 0(n),由2n2=r-q3let L[1..n + 1] and R[1..n2 + 1] be new arraysMaster定理可知，T（n）=4fori=ltoni0（nlgn），所以在最坏情况5Li=Ap+i-]下渐进时间复杂度为6forj=lto n20(nlgn)7R[] = A[q + j]8L[n+ 1] = 009R[n2 + 1] = 0010i=l11j=12fork=ptor13if L[] ≤ R[]14A[K] = L[]15i=i+l16else A[k] = R[]17j=j+l
第一问： 因为对于一个长度为n的数 组，最坏的情况是在最基 础的情况，也就是a=2时 要交换，且第一个For循环 要判断两次，而For循环那 里所话的时间为O(r)，即 为长度 ， 所 以 有 式 子 𝑇 𝑛 = 2𝑇 𝑛 2 + 𝑂(𝑛)，由 Master定理可知，𝑇 𝑛 = 𝑂(𝑛𝑙𝑔𝑛)，所以在最坏情况 下 渐 进 时 间 复 杂 度 为 𝑂(𝑛𝑙𝑔𝑛)
第二问：该问题本身的难度是nlgn。因为把石头按重量排序，相当于找出一个排序，而每进行一次比较，相当于得到一个序关系。那么，这个问题可以被转化成二叉树，每进行一次比较相当于一个内部节点，每种排斯特林公式序相当于一个叶节点。因为一共有n！种排序，所以有n！个叶节点，所以有2h-1 ≤n! < 2h而n！~V2元n("），所以有V2元)g2n+10(n+)g2+1F所以有h=0（nlgn）。又因为每一层都需要经过一个节点，即进行一次判断，所以难度为（nlgn）
第二问： 该问题本身的难度是𝛩𝑛𝑙𝑔𝑛。因为把石头按重量排序，相当于找出一个 排序，而每进行一次比较，相当于得到一个序关系。那么，这个问题 可以被转化成二叉树，每进行一次比较相当于一个内部节点，每种排 序相当于一个叶节点。 因为一共有𝑛!种排序，所以有𝑛!个叶节点，所以有 2 ℎ−1 ≤ 𝑛! < 2 ℎ 而𝑛! ≈ 2𝜋𝑛( 𝑛 𝑒 ) 𝑛，所以有 𝑛 + 1 2 log2 𝑛 + log2 2𝜋 𝑒 𝑛 < ℎ ≤ 𝑛 + 1 2 log2 𝑛 + log2 2𝜋 𝑒 𝑛 + 1 所以有ℎ = Θ(𝑛𝑙𝑔𝑛)。又因为每一层都需要经过一个节点，即进行一次 判断，所以难度为Θ(𝑛𝑙𝑔𝑛)