比较排序的平均情况下界

在本问题中，我们来证明给定n个不同的输入元素，对于任何确定或随机的比较排序算法，其期望运行时间都有下界Ω(nlgn)。首先来分析一个确定的比较排序算法A，其决策树为TA。假设A的输入的每一种排列都是等可能的。

a) 假设TA的每个叶结点都标以在给定的随机输入下到达该结点的概率。证明：恰有n!个叶结点标有1/n!，其他的标有0。

对于一个基于比较的排序算法A，不存在两个输入序列使之到达决策树的一个相同的叶子，所以决策树TA必然至少有n!个叶子。对于每个可能的输入序列，当A是一个确定算法时，输入某个特定的序列必然总是到达TA的同一个叶子，所以TA最多只有n!个叶子。因此TA有n!个叶子与每个可能的输入序列一一对应。对于n!个叶子，到达每一个叶子的可能性为1/n!，因为n!个可能的输入序列中任意一个出现的可能性都是1/n!。

b) 设D(T）表示一棵决策树T的外路径长度，也就是说，D(T)是T的所有叶结点深度的和。设T为一棵决策树，其叶子数k>1，并设RT和LT为T的右子树和左子树。证明：D(T)=D(RT)+D(LT)+k。

如果 k>1，则T的根一定不是叶子。这意味着T的所有叶子都在LT和RT中。因为每个叶子在LT或者RT中的深度h+1才是在T中的深度，所以 D(T)=D(LT)+D(RT)+k。设dT(x)=x结点在T中的深度。
于是：
D(T)=∑dT(x) (x∈leaves(T))
    =∑dT(x) (x∈leaves(LT)) + ∑dT(x) (x∈leaves(RT))
    =∑(dLT(x)+1) (x∈leaves(LT)) + ∑(dRT(x)+1) (x∈leaves(RT))
    =∑dLT(x) (x∈leaves(LT)) + ∑dRT(x) (x∈leaves(RT)) + ∑1 (x∈leaves(T))
    =D(LT)+D(RT)+k。

c) 设d(k)为所有具有k>1个叶结点的决策树D(T)的最小值。证明：d(k)=min(1<=i<=k-1){d(i)+d(k-i)+k}。

要证明d(k)=min(1<=i<=k-1){d(i)+d(k-i)+k}需证明
d(k)<=min(1<=i<=k-1){d(i)+d(k-i)+k}
且
d(k)>=min(1<=i<=k-1){d(i)+d(k-i)+k}
要证明d(k)<=min(1<=i<=k-1){d(i)+d(k-i)+k}，我们只需证明i=1, 2, ..., k-1时d(k)<=d(i)+d(k-i)+k。对于任意i(1<=i<=k-1)我们可以发现RT有i个叶子，LT有k-i个叶子，于是D(RT)=d(i)，D(LT)=d(k-i)。构造T使得RT和LT分别为T的右子树和左子树。于是：
d(k)<=D(T)
    =D(RT)+D(LT)+k
    =d(i)+d(k-i)+k
要证明d(k)>=min(1<=i<=k-1){d(i)+d(k-i)+k}，我们只需证明存在i=1, 2, ..., k-1使d(k)>=d(i)+d(k-i)+k。设k个叶子的T的D(T)=d(k)，让RT有i个叶子，LT有k-i个叶子。于是：
d(k)=D(T)
    =D(RT)+D(LT)+k
    >=d(i)+d(k-i)+k

d) 证明：对k的某一给定值(k>1)的范围1<=i<=k-1内的值，函数ilgi+(k-i)lg(k-i)在i=k/2处取得最小值。总结d(k)=Ω(klgk)。

设fk(i)=ilgi+(k-i)lg(k-i)。要找出fk取最小值时的i，就是找出fk的导数等于零时i的取值：
fk'(i)=d((ilni+(k-i)ln(k-i))/ln2)/di
      =(lni+1-ln(k-i)-1)/ln2
      =(lni-ln(k-i))/ln2
i=k/2时fk'(i)=0。要验证这的确是最小值，只需检测fk的二阶导在i=k/2时是否是正数：
fk''(i)=d((lni-ln(k-i))/ln2)/di
       =(1/i+1/(k-i))/ln2
fk''(k/2)=(2/k+2/k)/ln2
         =4/(k*ln2)>0 (k>1)
现在我们用带入法证明d(k)=Ω(klgk)。对于任意常数c，d(1)>=0=c*1*lg1。接下来，我们假定d(i)>cilgi (1<=i<=k-1)，c是一个已定的常数。
d(k)=min(1<=i<=k-1){d(i)+d(k-i)+k}
    >=min(1<=i<=k-1){c(ilgi+(k-i)lg(k-i))+k}
    =min(1<=i<=k-1){cfk(i)+k}
    =c(k/2*lg(k/2)(k-k/2)lg(k-k/2))+k
    =cklg(k/2)+k
    =c(klgk-k)+k
    =cklgk+(k-ck)
    >=cklgk
所以 d(k)=Ω(klgk)。

e) 证明：D(TA)=Ω(n!lg(n!))，并给出排序n个元素的期望时间为Ω(nlgn)的结论。

TA拥有n!个叶子，于是D(TA)>=d(n!)=Ω(n!lg(n!))。
D(TA)表示决策树所有输入序列的路径长度，这个路径长度与运行时间成比例。每种排列出现的概率都是1/n!。于是期望运行时间为：
Ω(n!lg(n!))/n!=Ω(lg(n!))=Ω(nlgn)。