概率论与数理统计 (Spring 2023)/Average-case analysis of QuickSort: Difference between revisions
(20 intermediate revisions by the same user not shown) | |||
Line 18: | Line 18: | ||
= 快速排序算法的平均复杂度分析 I(基于全期望法则)= | = 快速排序算法的平均复杂度分析 I(基于全期望法则)= | ||
令随机变量<math>X_n</math> | 令随机变量<math>X_n</math>表示在随机输入<math>A</math>下,快速排序算法使用的总比较次数。同时令<math>t(n)=\mathbb{E}[X_n]</math>表示其期望。正如刚刚解释的,<math>t(n)</math>是良定义的,因为期望值<math>\mathbb{E}[X_n]</math>仅与<math>n</math>有关。 | ||
对<math>1\le i\le n</math>,定义<math>B_i</math>为如下事件: | 对<math>1\le i\le n</math>,定义<math>B_i</math>为如下事件: | ||
Line 80: | Line 80: | ||
我们有若干种方法从这一递归式获得关于<math>t(n)=\mathbb{E}[X_n]</math>的真相: | 我们有若干种方法从这一递归式获得关于<math>t(n)=\mathbb{E}[X_n]</math>的真相: | ||
* 一种是使用'''生成函数'''等工具来求解这样的递归方程,例如使用[[组合数学_(Fall_2023)/Generating_functions#Analysis_of_Quicksort|'''本学期组合数学课上的分析''']],最终可精确解出<math>t(n)=2(n+1)H(n)-4n</math>,此处<math>H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1)</math>为第<math>n</math>个[https://en.wikipedia.org/wiki/Harmonic_number 调和数]; | * 一种是使用'''生成函数'''等工具来求解这样的递归方程,例如使用[[组合数学_(Fall_2023)/Generating_functions#Analysis_of_Quicksort|'''本学期组合数学课上的分析''']],最终可精确解出<math>t(n)=2(n+1)H(n)-4n</math>,此处<math>H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1)</math>为第<math>n</math>个[https://en.wikipedia.org/wiki/Harmonic_number 调和数]; | ||
* 另一种是采用'''数学归纳法'''来对我们猜想的关于<math>t(n)</math>的界进行验证,例如从<math>t(n)\le c n \ln n</math> | * 另一种是采用'''数学归纳法'''来对我们猜想的关于<math>t(n)</math>的界进行验证,例如从<math>t(n)\le c n \ln n</math>的归纳假设出发,尝试使<math>c</math>尽量小。令该归纳假设对于所有<math>0\le i<n</math>都成立,则对于<math>t(n)</math>,根据递归式因此有: | ||
:<math> | |||
\begin{align} | |||
t(n) | |||
&= | |||
n-1+\frac{2}{n}\sum_{i=0}^{n-1}t(i)\\ | |||
&\le | |||
n-1+\frac{2c}{n}\sum_{i=1}^{n-1}i \ln i &&\text{(归纳假设)}\\ | |||
&\le | |||
n-1+\frac{2c}{n}\int_{1}^nx \ln x\,\mathrm{d}x &&\text{(求和的积分上界)}\\ | |||
&= | |||
n-1+\frac{c}{2n}\left(2n^2\ln n-n^2+1\right)\\ | |||
&= | |||
cn\ln n-\left(\frac{c}{2}-1\right)n-1+\frac{c}{2n} | |||
\end{align} | |||
</math> | |||
设<math>c=2</math>时,有<math>t(n)\le cn\ln n-\left(\frac{c}{2}-1\right)n-1+\frac{c}{2n}\le 2 n \ln n</math>对于所有<math>n\ge 1</math>总是成立。 | |||
= 快速排序算法的平均复杂度分析 II(基于期望的线性)= | = 快速排序算法的平均复杂度分析 II(基于期望的线性)= | ||
令随机变量<math>X</math> | 令随机变量<math>X</math>表示在随机输入<math>A</math>下,快速排序算法使用的总比较次数。我们希望分析得到期望<math>\mathbb{E}[X]</math>的上界。 | ||
假设输入数组<math>A</math>中的元素,在从小到大排序之后为<math>a_1<a_2<\cdots a_n</math>。 | 假设输入数组<math>A</math>中的元素,在从小到大排序之后为<math>a_1<a_2<\cdots a_n</math>。 | ||
Line 110: | Line 126: | ||
事件<math>A_{ij}</math>的发生与否,由如下的递归随机过程确定: | 事件<math>A_{ij}</math>的发生与否,由如下的递归随机过程确定: | ||
# 在当前输入元素中按均匀分布随机选择'''pivot''' | # 在当前输入元素中按均匀分布随机选择'''pivot'''元素。如果刚好选中<math>a_i</math>或<math>a_j</math>二者之一,那么<math>a_i</math>与<math>a_j</math>之间必被比较(因为'''pivot'''会与当前数组内的所有元素进行比较)。此情况下,事件<math>A_{ij}</math>确定发生。 | ||
# 如果<math>a_i<</math>'''pivot'''<math><a_j</math>,即'''pivot'''取值在<math>a_i</math>与<math>a_j</math>之间,此时<math>a_i</math>与<math>a_j</math>会被大小居于其中间的'''pivot'''元素分别分流到子数组<math>L</math>与<math>R</math>中,且在之后的递归调用中永不再见,因此不会被比较。此情况下,事件<math>A_{ij}</math>确定不发生。 | # 如果<math>a_i<</math>'''pivot'''<math><a_j</math>,即'''pivot'''取值在<math>a_i</math>与<math>a_j</math>之间,此时<math>a_i</math>与<math>a_j</math>会被大小居于其中间的'''pivot'''元素分别分流到子数组<math>L</math>与<math>R</math>中,且在之后的递归调用中永不再见,因此不会被比较。此情况下,事件<math>A_{ij}</math>确定不发生。 | ||
# '''pivot'''选中了比<math>a_i</math>更小或者比<math>a_j</math>更大的元素,在此情况下<math>a_i</math>与<math>a_j</math>,连同它们之间的所有元素<math>\{a_k\mid i<k<j\}</math>,都会被分到同一个子数组<math>L</math>(假如'''pivot'''<math> | # 如果'''pivot'''选中了比<math>a_i</math>更小或者比<math>a_j</math>更大的元素,在此情况下<math>a_i</math>与<math>a_j</math>,连同它们之间的所有元素<math>\{a_k\mid i<k<j\}</math>,都会被分到同一个子数组<math>L</math>(假如'''pivot'''<math>>a_j</math>)或者<math>R</math>(假如'''pivot'''<math><a_i</math>)中。而此时<math>A_{ij}</math>的发生与否尚未能在这一层递归调用中确定,则需进入下一层递归调用,将当前输入数组改为<math>a_i</math>与<math>a_j</math>所同属的那个子数组(即<math>L</math>如果'''pivot'''<math>>a_j</math>,<math>R</math>如果'''pivot'''<math><a_i</math>),然后回到(1)重复。 | ||
不难看出该递归过程跟踪模拟了事件<math>A_{ij}</math>的发生与否,在快速排序算法的递归调用过程中,是如何被确定下来的。 | 不难看出该递归过程跟踪模拟了事件<math>A_{ij}</math>的发生与否,在快速排序算法的递归调用过程中,是如何被确定下来的。 | ||
因此,可以得出:<math>A_{ij}</math>发生,当且仅当在上述情况(1)或(2)之一发生的前提下有(1)发生。 | 因此,可以得出:<math>A_{ij}</math>发生,当且仅当在上述情况(1)或(2)之一发生的前提下有(1)发生。 | ||
除此之外,如下两个观察通过递归验证易得: | 除此之外,如下两个观察通过递归验证易得: | ||
* 当<math>a_i</math>与<math>a_j</math>同属于当前递归调用的输入数组时,它们之间的所有元素<math>\{a_k\mid i<k<j\}</math>也属于该数组; | * 当<math>a_i</math>与<math>a_j</math>同属于当前递归调用的输入数组时,它们之间的所有元素<math>\{a_k\mid i<k<j\}</math>也属于该数组; | ||
* 在任何递归调用中,'''pivot''' | * 在任何递归调用中,'''pivot'''始终在当前输入数组中均匀分布——这也可由'''性质一'''所述的输入分布的递归不变性得到。 | ||
综上可得: | 综上可得: | ||
:<math>\Pr(A_{ij})=\Pr(\mathsf{pivot}\in\{a_i,a_j\}\mid\mathsf{pivot}\in\{a_i,a_{i+1},\ldots,a_{j}\})=\frac{2}{j-i+1}</math>. | :<math>\Pr(A_{ij})=\Pr(\mathsf{pivot}\in\{a_i,a_j\}\mid\mathsf{pivot}\in\{a_i,a_{i+1},\ldots,a_{j}\})=\frac{2}{j-i+1}</math>. | ||
Line 129: | Line 145: | ||
&= | &= | ||
\sum_{i<j}\Pr(A_{ij})\\ | \sum_{i<j}\Pr(A_{ij})\\ | ||
& | &=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\frac{2}{j-i+1}\\ | ||
&= \sum_{i=1}^n\sum_{k=2}^{n-i+1}\frac{2}{k} & & (\text{令 }k=j-i+1)\\ | &= \sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\frac{2}{k} & & (\text{令 }k=j-i+1)\\ | ||
&\le \sum_{i=1}^n\sum_{k=1}^{n}\frac{2}{k}\\ | &\le \sum_{i=1}^n\sum_{k=1}^{n}\frac{2}{k}\\ | ||
&= 2n\sum_{k=1}^{n}\frac{1}{k}\\ | &= 2n\sum_{k=1}^{n}\frac{1}{k}\\ | ||
Line 136: | Line 152: | ||
\end{align}</math> | \end{align}</math> | ||
此处<math>H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1)</math>为第<math>n</math>个[http://en.wikipedia.org/wiki/Harmonic_number 调和数]。 | 此处<math>H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1)</math>为第<math>n</math>个[http://en.wikipedia.org/wiki/Harmonic_number 调和数]。 | ||
如果更加仔细一些,我们甚至可以计算出总比较次数期望<math>\mathbb{E}[X]</math>的精确值: | |||
:<math>\begin{align} | |||
\mathbb{E}\left[X\right] | |||
&= | |||
\sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\frac{2}{k}\\ | |||
&= | |||
\sum_{j=2}^n\sum_{k=2}^{j}\frac{2}{k} && \text{(令$j=n-i+1$)}\\ | |||
&= | |||
\sum_{k=2}^{n}\frac{2(n-k+1)}{k} && \text{(交换求和顺序)}\\ | |||
&= | |||
\sum_{k=2}^{n}\left(\frac{2(n+1)}{k}-2\right)\\ | |||
&= | |||
2(n+1)\sum_{k=2}^{n}\frac{1}{k}-2(n-1)\\ | |||
&= | |||
2(n+1)\sum_{k=1}^{n}\frac{1}{k}-4n\\ | |||
&= | |||
2(n+1)H(n)-4n. | |||
\end{align}</math> |
Latest revision as of 03:26, 13 April 2023
快速排序(Quicksort)是由Tony Hoare发现的排序算法。该算法的伪代码描述如下(为方便起见,假设数组元素互不相同——更一般情况的分析易推广得到):
QSort(A): 输入A[1...n]是存有n个不同数字的数组 if n>1 then pivot = A[1]; 将A中<pivot的元素存于数组L,将A中>pivot的元素存于数组R; \\保持内部元素之间相对顺序 递归调用QSort(L)和QSort(R);
该伪代码描述省略了对数组的存取归并等具体实现的交代。可以不妨认为算法中的[math]\displaystyle{ L }[/math]和[math]\displaystyle{ R }[/math]其实就分别是原数组[math]\displaystyle{ A }[/math]的前半部分[math]\displaystyle{ A[1...i-1] }[/math]和后半部分[math]\displaystyle{ A[i...n] }[/math],其中[math]\displaystyle{ i }[/math]表示pivot(“基准”、“轴点”、“分水岭”元素)在数组[math]\displaystyle{ A }[/math]中的序数,即pivot是数组[math]\displaystyle{ A }[/math]中第[math]\displaystyle{ i }[/math]小的数。
作为基于比较的(comparison-based)排序算法,我们将算法进行的元素间的比较次数作为算法的复杂性度量。在最坏情况(worst-case)输入下,我们描述的“快速排序”算法所使用的比较次数可以达到[math]\displaystyle{ \Theta(n^2) }[/math]。而且有趣的是,这一[math]\displaystyle{ \Omega(n^2) }[/math]的复杂度下界是在输入数组是一个已排好序的数组时达到的:此时pivot会将数组[math]\displaystyle{ A }[/math]划分为大小极不平衡的子数组[math]\displaystyle{ L }[/math]和[math]\displaystyle{ R }[/math],递归树也因此极不平衡,而算法使用的比较次数可因此达到[math]\displaystyle{ (n-1)+(n-2)+(n-3)+\cdots+1=\Omega(n^2) }[/math]。
现在我们来分析这一算法的平均情况(average-case)复杂度。 令输入数组[math]\displaystyle{ A }[/math]为[math]\displaystyle{ n }[/math]个元素的均匀分布的随机排列。如下性质不难递归验证:
性质一(输入分布的递归不变性) - 作为基于比较的排序算法,快速排序算法的行为仅与输入数组[math]\displaystyle{ A }[/math]中元素的相对顺序有关,而与[math]\displaystyle{ A }[/math]中元素的具体数值无关。
- 进一步地,在算法的每次递归调用中,其输入数组中元素的相对顺序,符合该数量元素的所有排列上的均匀分布。
快速排序算法的平均复杂度分析 I(基于全期望法则)
令随机变量[math]\displaystyle{ X_n }[/math]表示在随机输入[math]\displaystyle{ A }[/math]下,快速排序算法使用的总比较次数。同时令[math]\displaystyle{ t(n)=\mathbb{E}[X_n] }[/math]表示其期望。正如刚刚解释的,[math]\displaystyle{ t(n) }[/math]是良定义的,因为期望值[math]\displaystyle{ \mathbb{E}[X_n] }[/math]仅与[math]\displaystyle{ n }[/math]有关。
对[math]\displaystyle{ 1\le i\le n }[/math],定义[math]\displaystyle{ B_i }[/math]为如下事件:
- pivot在数组[math]\displaystyle{ A }[/math]中是第[math]\displaystyle{ i }[/math]小的元素。
则[math]\displaystyle{ B_1,B_2,\ldots,B_n }[/math]构成了对所有情况(样本空间)的一个划分。且每个事件[math]\displaystyle{ B_i }[/math]发生的概率有:
- [math]\displaystyle{ \Pr(B_i)=\frac{(n-1)!}{n!}=\frac{1}{n} }[/math].
这是因为事件[math]\displaystyle{ B_i }[/math]等价于一个均匀分布的随机排列[math]\displaystyle{ \pi:[n]\xrightarrow[\text{onto}]{\text{1-1}}[n] }[/math]有[math]\displaystyle{ \pi(1)=i }[/math],而这件事的概率为[math]\displaystyle{ \frac{1}{n} }[/math]。
因此,根据全期望法则(law of total expectation),有:
- [math]\displaystyle{ \begin{align} t(n) = \mathbb{E}[X_n] &= \sum_{i=1}^n\mathbb{E}[X_n\mid B_i]\Pr(B_i) = \frac{1}{n}\sum_{i=1}^n\mathbb{E}[X_n\mid B_i] \end{align} }[/math].
而当事件[math]\displaystyle{ B_i }[/math]发生时,即当pivot恰为数组[math]\displaystyle{ A }[/math]中第[math]\displaystyle{ i }[/math]小的元素, 算法会将[math]\displaystyle{ A }[/math]中比pivot小的[math]\displaystyle{ (i-1) }[/math]个元素放入子数组[math]\displaystyle{ L }[/math]、将比pivot大的[math]\displaystyle{ (n-i) }[/math]个元素放入子数组[math]\displaystyle{ R }[/math],这总共会花费[math]\displaystyle{ n-1 }[/math]次比较。 而且,根据性质一中所述的输入分布的递归不变性,递归调用QSort[math]\displaystyle{ (L) }[/math]和QSort[math]\displaystyle{ (R) }[/math]各自所使用的总比较次数分别为[math]\displaystyle{ X_{i-1} }[/math]和[math]\displaystyle{ X_{n-i} }[/math]。 综上所述,有如下恒等关系:
- [math]\displaystyle{ \mathbb{E}[X_n\mid B_i] = \mathbb{E}[n-1+X_{i-1}+X_{n-i}] }[/math].
因此,上述全期望因此可被计算如下:
- [math]\displaystyle{ \begin{align} t(n) = \mathbb{E}[X_n] &= \frac{1}{n}\sum_{i=1}^n\mathbb{E}[X_n\mid B_i]\\ &= \frac{1}{n}\sum_{i=1}^n\mathbb{E}[n-1+X_{i-1}+X_{n-i}]\\ &= n-1+\frac{2}{n}\sum_{i=0}^{n-1}\mathbb{E}[X_{i}] &\text{(根据期望的线性)}\\ &= n-1+\frac{2}{n}\sum_{i=0}^{n-1}t(i). \end{align} }[/math]
我们因此建立了平均复杂度[math]\displaystyle{ t(n)=\mathbb{E}[X_n] }[/math]的如下递归式:
- [math]\displaystyle{ \begin{align} t(n) &= n-1+\frac{2}{n}\sum_{i=0}^{n-1}t(i) && \text{if }n\gt 1;\\ t(n) &= 0 && \text{if }0\le n\le 1. \end{align} }[/math]
我们有若干种方法从这一递归式获得关于[math]\displaystyle{ t(n)=\mathbb{E}[X_n] }[/math]的真相:
- 一种是使用生成函数等工具来求解这样的递归方程,例如使用本学期组合数学课上的分析,最终可精确解出[math]\displaystyle{ t(n)=2(n+1)H(n)-4n }[/math],此处[math]\displaystyle{ H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1) }[/math]为第[math]\displaystyle{ n }[/math]个调和数;
- 另一种是采用数学归纳法来对我们猜想的关于[math]\displaystyle{ t(n) }[/math]的界进行验证,例如从[math]\displaystyle{ t(n)\le c n \ln n }[/math]的归纳假设出发,尝试使[math]\displaystyle{ c }[/math]尽量小。令该归纳假设对于所有[math]\displaystyle{ 0\le i\lt n }[/math]都成立,则对于[math]\displaystyle{ t(n) }[/math],根据递归式因此有:
- [math]\displaystyle{ \begin{align} t(n) &= n-1+\frac{2}{n}\sum_{i=0}^{n-1}t(i)\\ &\le n-1+\frac{2c}{n}\sum_{i=1}^{n-1}i \ln i &&\text{(归纳假设)}\\ &\le n-1+\frac{2c}{n}\int_{1}^nx \ln x\,\mathrm{d}x &&\text{(求和的积分上界)}\\ &= n-1+\frac{c}{2n}\left(2n^2\ln n-n^2+1\right)\\ &= cn\ln n-\left(\frac{c}{2}-1\right)n-1+\frac{c}{2n} \end{align} }[/math]
设[math]\displaystyle{ c=2 }[/math]时,有[math]\displaystyle{ t(n)\le cn\ln n-\left(\frac{c}{2}-1\right)n-1+\frac{c}{2n}\le 2 n \ln n }[/math]对于所有[math]\displaystyle{ n\ge 1 }[/math]总是成立。
快速排序算法的平均复杂度分析 II(基于期望的线性)
令随机变量[math]\displaystyle{ X }[/math]表示在随机输入[math]\displaystyle{ A }[/math]下,快速排序算法使用的总比较次数。我们希望分析得到期望[math]\displaystyle{ \mathbb{E}[X] }[/math]的上界。
假设输入数组[math]\displaystyle{ A }[/math]中的元素,在从小到大排序之后为[math]\displaystyle{ a_1\lt a_2\lt \cdots a_n }[/math]。 对[math]\displaystyle{ 1\le i\lt j\le n }[/math],令布尔值随机变量[math]\displaystyle{ I_{ij}=I(A_{ij})\in\{0,1\} }[/math]指示如下事件的发生:
- [math]\displaystyle{ A_{ij} }[/math]:元素[math]\displaystyle{ a_i }[/math]和[math]\displaystyle{ a_j }[/math]在算法运行过程中被比较了。
容易验证:在算法运行过程中,任何元素对[math]\displaystyle{ a_i }[/math]和[math]\displaystyle{ a_j }[/math]之间至多只会进行一次比较。 因此总比较次数[math]\displaystyle{ X }[/math]可被计算如下:
- [math]\displaystyle{ X=\sum_{i\lt j}I_{ij} }[/math].
根据期望的线性(linearity of expectation):
- [math]\displaystyle{ \mathbb{E}[X]=\sum_{i\lt j}\mathbb{E}[I_{ij}]=\sum_{i\lt j}\Pr(A_{ij}) }[/math].
因此接下来,仅需要针对每一对具体的[math]\displaystyle{ 1\le i\lt j\le n }[/math],计算概率:
- [math]\displaystyle{ \Pr(A_{ij})=\Pr(a_i\text{和}a_j\text{在算法中进行了比较}) }[/math].
而事件[math]\displaystyle{ A_{ij} }[/math]发生,当且仅当:在某次递归调用中,[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]同属于当前输入数组,且pivot恰好选中[math]\displaystyle{ a_i }[/math]或[math]\displaystyle{ a_j }[/math]二者之一。 注意到:假如[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]同属于当前输入数组,则当前数组必然也同时包含它们之间的所有元素[math]\displaystyle{ \{a_k\mid i\lt k\lt j\} }[/math]; 同时,事件[math]\displaystyle{ A_{ij} }[/math]的发生与否,仅当首次在某递归调用中pivot选中了[math]\displaystyle{ \{a_k\mid i\le k\le j\} }[/math]中的元素,才会确定。 综上,于是有:
- [math]\displaystyle{ \Pr(A_{ij})=\Pr(\mathsf{pivot}\in\{a_i,a_j\}\mid\mathsf{pivot}\in\{a_i,a_{i+1},\ldots,a_{j}\})=\frac{2}{j-i+1} }[/math].
如果你认为该证明不够详细。这里再提供一个对于上述事实的详细证明。
定下任意一对具体的[math]\displaystyle{ 1\le i\lt j\le n }[/math]。 在算法运行之初(顶层递归调用),元素[math]\displaystyle{ a_i }[/math]与[math]\displaystyle{ a_j }[/math]显然有[math]\displaystyle{ a_i\lt a_j }[/math],且同属于当前递归调用的输入数组[math]\displaystyle{ A }[/math]。 事件[math]\displaystyle{ A_{ij} }[/math]的发生与否,由如下的递归随机过程确定:
不难看出该递归过程跟踪模拟了事件[math]\displaystyle{ A_{ij} }[/math]的发生与否,在快速排序算法的递归调用过程中,是如何被确定下来的。 因此,可以得出:[math]\displaystyle{ A_{ij} }[/math]发生,当且仅当在上述情况(1)或(2)之一发生的前提下有(1)发生。 除此之外,如下两个观察通过递归验证易得:
综上可得:
|
算法总比较次数的期望[math]\displaystyle{ \mathbb{E}[X] }[/math]可被计算如下:
- [math]\displaystyle{ \begin{align} \mathbb{E}\left[X\right] &= \sum_{i\lt j}\Pr(A_{ij})\\ &=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\frac{2}{j-i+1}\\ &= \sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\frac{2}{k} & & (\text{令 }k=j-i+1)\\ &\le \sum_{i=1}^n\sum_{k=1}^{n}\frac{2}{k}\\ &= 2n\sum_{k=1}^{n}\frac{1}{k}\\ &= 2n H(n). \end{align} }[/math]
此处[math]\displaystyle{ H(n)=\sum_{k=1}^{n}\frac{1}{k}= \ln n+O(1) }[/math]为第[math]\displaystyle{ n }[/math]个调和数。
如果更加仔细一些,我们甚至可以计算出总比较次数期望[math]\displaystyle{ \mathbb{E}[X] }[/math]的精确值:
- [math]\displaystyle{ \begin{align} \mathbb{E}\left[X\right] &= \sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\frac{2}{k}\\ &= \sum_{j=2}^n\sum_{k=2}^{j}\frac{2}{k} && \text{(令$j=n-i+1$)}\\ &= \sum_{k=2}^{n}\frac{2(n-k+1)}{k} && \text{(交换求和顺序)}\\ &= \sum_{k=2}^{n}\left(\frac{2(n+1)}{k}-2\right)\\ &= 2(n+1)\sum_{k=2}^{n}\frac{1}{k}-2(n-1)\\ &= 2(n+1)\sum_{k=1}^{n}\frac{1}{k}-4n\\ &= 2(n+1)H(n)-4n. \end{align} }[/math]