全期望公式
条件期望公式：
$$
\mathbb{E}\left[ X|A \right] =\sum_x{x\cdot Pr\left( X=x|A \right)}
$$
全期望公式：
$$
\mathbb{E}\left[ X \right] =\sum_{i=1}^n{\mathbb{E}\left[ X|B_i \right] \cdot Pr\left( B_i \right)}
$$
证明：
$$
Proof:\mathbb{E}\left[ X \right] =\sum_x{x\cdot Pr\left( X=x \right)}=\sum_x{x\cdot}\sum_{i=1}^n{Pr\left( X=x|B_i \right) \cdot Pr\left( B_i \right)}
$$
$$
=\sum_{i=1}^n{Pr\left( B_i \right)}\sum_x{x\cdot Pr\left( X=x|B_i \right)}=\sum_{i=1}^n{\mathbb{E}\left[ X|B_i \right] \cdot Pr\left( B_i \right)}
$$
令时间复杂度$t\left( n \right) =\mathbb{E}\left( X_n \right) $，其中$X_n$是在$Qsort(A)$中对$n$个不同数的均匀随机排列$A$使用的比较次数。令事件$B_i$为序列$A\left[ 1 \right] $是序列$A$中第$i$小的数字。
此时序列可以分为两个部分较小的集合的容量是$i − 1$，较大的集合的容量是$n − i$且初值需要经过$n – 1$次比较，故由全期望公式可得：
$$
t\left( n \right) =\mathbb{E}\left( X_n \right) =\sum_{i=1}^n{\mathbb{E}\left[ X_n|B_i \right] \cdot Pr\left( B_i \right)}
$$
$$
=\frac{1}{n}\sum_{i=1}^n{\mathbb{E}\left[ n-1+X_{i-1}+X_{j-i} \right] =n-1+\frac{2}{n}\sum_{i=0}^{n-1}{t\left( i \right)}}
$$
期望的上下界分析
对于一个无向图$G\left( V,E \right) $，最大割是指使得点集$S\subseteq V$满足$\left\{ \left\{ u,v \right\} \in E|u\in s\land v\ni s \right\} $成立的最大边集，它是一个$NP-hard$的问题。可以证明总存在一个最大割且容量$\left| S \right|>\left| E \right|/2$。
