算法导论第7章思考题
c. E[T(n)]=E [ ∑ q = 1 n X q ( T ( q − 1 ) + T ( n − q ) + Θ ( n ) ) ] \left[\sum\limits_{q=1}^nX_q(T(q-1)+T(n-q)+\Theta(n))\right] [q=1∑nXq(T(q−1)+T(n−q)+Θ(n))]
证明上式可重写为：E[T(n)]= 2 n ∑ q = 2 n − 1 {2\over n}\sum\limits_{q=2}^{n-1} n2q=2∑n−1E[T(q)]+ Θ \Theta Θ(n)
E [ T ( n ) ] = E [ ∑ q = 1 n X q ( T ( q − 1 ) + T ( n − q ) + Θ ( n ) ) ] = ∑ q = 1 n E [ X q ( T ( q − 1 ) + T ( n − q ) + Θ ( n ) ) ] = ∑ q = 1 n E [ T ( q − 1 ) + T ( n − q ) ] + Θ ( n ) n = Θ ( n ) + 1 n ∑ q = 1 n E [ T ( q − 1 ) + T ( n − q ) ] = Θ ( n ) + 2 n ∑ q = 1 n E [ T ( q − 1 ) ] = Θ ( n ) + 2 n ∑ q = 2 n − 1 E [ T ( q ) ] \begin{aligned}E[T(n)]&=E\left[\sum\limits_{q=1}^nX_q(T(q-1)+T(n-q)+\Theta(n))\right]\\ &=\sum\limits_{q=1}^nE[X_q(T(q-1)+T(n-q)+\Theta(n))]\\ &=\sum\limits_{q=1}^n{E[T(q-1)+T(n-q)]+\Theta(n)\over n}\\ &=\Theta(n)+{1\over n}\sum\limits_{q=1}^nE[T(q-1)+T(n-q)]\\ &=\Theta(n)+{2\over n}\sum\limits_{q=1}^nE[T(q-1)]\\ &=\Theta(n)+{2\over n}\sum\limits_{q=2}^{n-1}E[T(q)] \end{aligned} E[T(n)]=E[q=1∑nXq(T(q−1)+T(n−q)+Θ(n))]=q=1∑nE[Xq(T(q−1)+T(n−q)+Θ(n))]=q=1∑nnE[T(q−1)+T(n−q)]+Θ(n)=Θ(n)+n1q=1∑nE[T(q−1)+T(n−q)]=Θ(n)+n2q=1∑nE[T(q−1)]=Θ(n)+n2q=2∑n−1E[T(q)]