站群网站,贵州最新消息今天,多语言网站建设应注意哪些事项,学做网站论坛vip共享摘要: 拉马努金Q函数在算法分析中的应用#xff0c;初步体验 【对算法#xff0c;数学#xff0c;计算机感兴趣的同学#xff0c;欢迎关注我哈#xff0c;阅读更多原创文章】 我的网站#xff1a;潮汐朝夕的生活实验室 我的公众号#xff1a;算法题刷刷 我的知乎#x… 摘要: 拉马努金Q函数在算法分析中的应用初步体验 【对算法数学计算机感兴趣的同学欢迎关注我哈原创文章】 我的网站潮汐朝夕的生活实验室 我的公众号算法题刷刷 我的知乎潮汐朝夕 我的githubFennelDumplings 我的leetcodeFennelDumplings 各位好本文我们继续来讨论算法分析中的问题。
很多数组上的算法都与 1 ∼ n 1 \sim n 1∼n 的排列有关比如各种排序算法。在分析数组上的排序算法时排列上的各种概念对分析问题很有用比如逆序、圈、左向右最大值、上升、下降、游程、峰、谷等等。
本文我们看一下逆序的概念及其在冒泡排序的分析中的作用。然后我们解决一个相关的算法分析问题对于 1 ∼ N 1 \sim N 1∼N 的随机排列 N → ∞ N \rightarrow\infty N→∞ 时冒泡排序平均要跑多少趟。
首先给出结论 N → ∞ N \rightarrow\infty N→∞ 时冒泡排序平均扫描趟数为 N − π N 2 O ( 1 ) N - \sqrt{\frac{\pi N}{2}} O(1) N−2πN O(1)。
为了推导以上结论我们首先介绍一下排列中关于逆序、逆序数、逆序表的概念。然后介绍一下冒泡排序算法的流程然后根据逆序表的概念以及冒泡排序的流程我们将冒泡排序平均扫描趟数问题转化为逆序表的最大值的问题。
之后我们在逆序表上经过一些组合分析再结合数学期望的性质将问题的答案写成了一个和式。于是原问题最终转化为了一个和式的渐近估阶的问题。
然后引用拉马努金Q函数相关的结论对原和式化简使得我们可以比较容易地对简化后的和式进行渐近估阶得到最终结果。
排列的一些基本概念
记 p p 1 p 2 ⋅ ⋅ ⋅ p N p p_{1}p_{2}\cdot\cdot\cdot p_{N} pp1p2⋅⋅⋅pN 为 1 ∼ N 1 \sim N 1∼N 的一个排列。
逆序一个逆序是 i j i j ij 且 p i p j p_{i} p_{j} pipj 的一个数对。
逆序表记 q j q_{j} qj 表示 i ∈ [ 1.. j − 1 ] i \in [1..j-1] i∈[1..j−1] 中 p i p j p_{i} p_{j} pipj 的个数。 q q 1 q 2 ⋅ ⋅ ⋅ q N q q_{1}q_{2}\cdot\cdot\cdot q_{N} qq1q2⋅⋅⋅qN 成为排列 p p p 的逆序表。
逆序数记 σ ( p ) ∑ j 1 N q j \sigma(p) \sum\limits_{j1}\limits^{N}q_{j} σ(p)j1∑Nqj表示排列 p p p 的逆序数。
排列与逆序表的一一对应
由以上定义可以知道对于 1 ≤ j ≤ N 1 \leq j \leq N 1≤j≤N q j q_{j} qj 需要满足约束 0 ≤ q j j 0 \leq q_{j} j 0≤qjj。
给定满足该约束的任意一个序列 q q 1 q 2 ⋅ ⋅ ⋅ q N q q_{1}q_{2}\cdot\cdot\cdot q_{N} qq1q2⋅⋅⋅qN下面我们构造满足该逆序表 q q q 的排列 p p p。
对于 i N , N − 1 , ⋯ , 1 i N, N-1, \cdots, 1 iN,N−1,⋯,1置 p i p_{i} pi 为未曾用过的数中第 q i q_{i} qi 大的数即可从右到左构造 p p 1 p 2 ⋅ ⋅ ⋅ p N p p_{1}p_{2}\cdot\cdot\cdot p_{N} pp1p2⋅⋅⋅pN。
也就是说给定任意长为 N N N 的逆序表至少可以构造出一个满足该逆序表的 1 ∼ N 1 \sim N 1∼N 的排列下面我们说明该排列是唯一的。
由于 q i q_{i} qi 的取值范围 [ 0.. i − 1 ] [0..i-1] [0..i−1] 有 i i i 种可能因此共有 N ! N! N! 种可能的逆序表 q q 1 q 2 ⋅ ⋅ ⋅ q N q q_{1}q_{2}\cdot\cdot\cdot q_{N} qq1q2⋅⋅⋅qN。
另一方面我们熟知 1 ∼ N 1 \sim N 1∼N 的排列数为 N ! N! N!如果在 N ! N! N! 个长为 N N N 的逆序表中存在某个逆序表其对应的排列不唯一由鸽巢原理就会出现某个 1 ∼ N 1 \sim N 1∼N 的排列对应两个不同的逆序表的情况这与逆序表的定义矛盾。
因此长度为 N N N 的排列与逆序表之间存在一一对应关系。这对于我们分析冒泡排序非常有用。
冒泡排序算法
要对一个数组 p p p 排序可以重复扫描这个数组。在一趟扫描过程中假设扫描到 p [ i ] p[i] p[i] 时如果 p [ i ] p [ i 1 ] p[i] p[i 1] p[i]p[i1]则将 p [ i ] p[i] p[i] 与 p [ i 1 ] p[i1] p[i1] 交换然后扫描下一个。否则直接扫描下一个。
如果在某趟扫描完成时没有进行过任何交换也就是每个元素都不比它后面的元素大则排序就完成了。
由于每个交换都是两个相邻元素的交换因此交换之后逆序数减 1这样总的交换次数恰好是一个排列中的逆序数。
另一方面通过画图分析我们可以发现一趟扫描完成后逆序表中每个非零项的值都会减 1。当逆序表中所有项均为零时程序结束。
这就隐含了对一个排列的冒泡排序所需的趟数就等于逆序表中的最大元素。于是冒泡排序平均要跑多少趟就等同于问在 N ! N! N! 种可能的长为 N N N 的逆序表 q q 1 q 2 ⋅ ⋅ ⋅ q N q q_{1}q_{2}\cdot\cdot\cdot q_{N} qq1q2⋅⋅⋅qN 中最大值 max 1 ≤ j ≤ N q j \max\limits_{1\leq j \leq N} q_{j} 1≤j≤Nmaxqj 的平均值是多少。
逆序表中的最大值
对于 1 ∼ N 1 \sim N 1∼N 的排列给定 0 ≤ k ≤ N 0 \leq k \leq N 0≤k≤N考察所有项都小于 k k k 的逆序表的个数。
考察 q i q_{i} qi。如果 i ≤ k i \leq k i≤k q i q_{i} qi 可以取 [ 0.. i − 1 ] [0..i-1] [0..i−1] 的任意值。当 i k i k ik 时 q i q_{i} qi 可以取 [ 0.. k − 1 ] [0..k-1] [0..k−1] 之间的值。
于是 N ! N! N! 种长为 N N N 的逆序表中所有项都小于 k k k也就是最大项小于 k k k 的逆序表的个数为 k ! k N − k k!k^{N-k} k!kN−k。
因此 N ! N! N! 个长为 N 的逆序表中最大项大于等于 k k k 的概率为 1 − k ! k N − k N ! 1 - \frac{k!k^{N-k}}{N!} 1−N!k!kN−k。
记 Q Q Q 为随机的长为 N N N 的逆序表中的最大值于是我们已经得到 P ( Q ≥ k ) 1 − k ! k N − k N ! P(Q \geq k) 1 - \frac{k!k^{N-k}}{N!} P(Q≥k)1−N!k!kN−k。
下面我们要求 E [ Q ] E[Q] E[Q]。这需要用到通过累积分布函数求数学期望的性质。
由累计分布函数求数学期望
我们知道根据定义计算数学期望的一般方法如下。 X X X 为离散型分布律为 P ( X x ) P(Xx) P(Xx) E [ X ] ∑ x x P ( X x ) E[X] \sum\limits_{x}xP(Xx) E[X]x∑xP(Xx) X X X 为连续型概率密度函数为 f ( x ) f(x) f(x) E [ X ] ∫ x f ( x ) d x E[X] \int xf(x)\mathrm{d}x E[X]∫xf(x)dx
但如果随机变量 X X X 非负还可以有不经过分布律或概率密度函数的算法。
如果非负 X X X 为离散型且已知 P ( X ≥ n ) P(X \geq n) P(X≥n)那么有 E [ X ] ∑ n 0 ∞ P ( X ≥ n ) E[X] \sum\limits_{n0}\limits^{\infty}P(X\geq n) E[X]n0∑∞P(X≥n)
证明 E [ X ] ∑ x 0 ∞ x P ( X x ) ∑ x 0 ∞ ∑ n 0 x P ( X x ) ∑ n 0 ∞ ∑ x n ∞ P ( X x ) ∑ n 0 ∞ P ( X ≥ x ) \begin{aligned} E[X] \sum\limits_{x0}\limits^{\infty}xP(Xx) \\ \sum\limits_{x0}\limits^{\infty}\sum\limits_{n0}\limits^{x}P(Xx) \\ \sum\limits_{n0}\limits^{\infty}\sum\limits_{xn}\limits^{\infty}P(Xx) \\ \sum\limits_{n0}\limits^{\infty}P(X\geq x) \\ \end{aligned} E[X]x0∑∞xP(Xx)x0∑∞n0∑xP(Xx)n0∑∞xn∑∞P(Xx)n0∑∞P(X≥x) □ \Box □
类似地如果非负 X X X 为连续型且其累积分布函数为 F ( x ) F(x) F(x)那么有 E [ X ] ∫ 0 ∞ ( 1 − F ( x ) ) d x E[X] \int_{0}^{\infty}(1 - F(x))\mathrm{d}x E[X]∫0∞(1−F(x))dx
证明 E [ X ] ∫ 0 ∞ y f ( y ) d y ∫ 0 ∞ ∫ 0 y f ( y ) d x d y ∫ 0 ∞ ∫ x ∞ f ( y ) d y d x ∫ 0 ∞ ( 1 − F ( x ) ) d x \begin{aligned} E[X] \int_{0}^{\infty}yf(y)\mathrm{d}y \\ \int_{0}^{\infty}\int_{0}^{y}f(y)\mathrm{d}x\mathrm{d}y \\ \int_{0}^{\infty}\int_{x}^{\infty}f(y)\mathrm{d}y\mathrm{d}x \\ \int_{0}^{\infty}(1 - F(x))\mathrm{d}x \\ \end{aligned} E[X]∫0∞yf(y)dy∫0∞∫0yf(y)dxdy∫0∞∫x∞f(y)dydx∫0∞(1−F(x))dx □ \Box □
问题规约拉马努金Q函数
根据前面对逆序表的分析以及上述数学期望的性质长为 N N N 的逆序表的最大值的期望如下 ∑ k 0 N ( 1 − k ! k N − k N ! ) N 1 − ∑ k 0 N k ! k N − k N ! \sum\limits_{k0}\limits^{N}(1 - \frac{k!k^{N-k}}{N!}) N 1 - \sum\limits_{k0}\limits^{N}\frac{k!k^{N-k}}{N!} k0∑N(1−N!k!kN−k)N1−k0∑NN!k!kN−k
于是最初的问题最终归结到了对 ∑ k 0 N k ! k N − k N ! \sum\limits_{k0}\limits^{N}\frac{k!k^{N-k}}{N!} k0∑NN!k!kN−k 的渐近估阶。
对以上和式做下标变换 ∑ k 0 N k ! k N − k N ! ∑ k 0 N ( N − k ) ! ( N − k ) k N ! \sum\limits_{k0}\limits^{N}\frac{k!k^{N-k}}{N!} \sum\limits_{k0}\limits^{N}\frac{(N-k)!(N-k)^{k}}{N!} \\ k0∑NN!k!kN−kk0∑NN!(N−k)!(N−k)k
记 f N ( k ) ( N − k ) ! ( N − k ) k N ! f_{N}(k) \frac{(N-k)!(N-k)^{k}}{N!} fN(k)N!(N−k)!(N−k)k下面推导 f N ( k ) f_{N}(k) fN(k) f N ( k ) ( N − k ) ! ( N − k ) k N ! N − k N ⋅ N − k N − 1 ⋅ ⋅ ⋅ N − k N − k 1 ( 1 − k N ) ⋅ ( 1 − k − 1 N − 1 ) ⋅ ⋅ ⋅ ( 1 − 1 N − k 1 ) ∏ i 1 k ( 1 − i N − k i ) \begin{aligned} f_{N}(k) \frac{(N-k)!(N-k)^{k}}{N!} \\ \frac{N-k}{N}\cdot \frac{N-k}{N-1} \cdot\cdot\cdot \frac{N-k}{N-k1} \\ (1 - \frac{k}{N})\cdot (1 - \frac{k-1}{N-1}) \cdot\cdot\cdot (1 - \frac{1}{N-k1}) \\ \prod\limits_{i1}\limits^{k}(1 - \frac{i}{N-ki}) \\ \end{aligned} fN(k)N!(N−k)!(N−k)kNN−k⋅N−1N−k⋅⋅⋅N−k1N−k(1−Nk)⋅(1−N−1k−1)⋅⋅⋅(1−N−k11)i1∏k(1−N−kii)
后续的处理非常复杂需要对 k 较小和 k 很大的情况分别讨论比较冗长其完整推导过程与拉马努金 Q 函数的推导过程类似这里直接引用结论如下 ∑ k 0 N k ! k N − k N ! ∑ k 0 N f N ( k ) ∑ k 0 N e − k 2 2 N O ( 1 ) N → ∞ \sum\limits_{k0}\limits^{N}\frac{k!k^{N-k}}{N!} \sum\limits_{k0}\limits^{N}f_{N}(k) \sum\limits_{k0}\limits^{N}e^{-\frac{k^{2}}{2N}} O(1) \quad\quad N\rightarrow\infty k0∑NN!k!kN−kk0∑NfN(k)k0∑Ne−2Nk2O(1)N→∞
以后有时间可以再回来看一下上式的推导过程感兴趣的可以看《算法分析导论》或《计算机程序设计艺术》中关于拉马努金Q函数的内容。
积分逼近求和
下面对 ∑ k 0 ∞ e − k 2 2 N \sum\limits_{k0}\limits^{\infty}e^{-\frac{k^{2}}{2N}} k0∑∞e−2Nk2 进行估阶。记 h ( x ) e − x 2 2 N h(x) e^{-\frac{x^{2}}{2N}} h(x)e−2Nx2。可以用积分逼近求和 ∑ k 0 ∞ e − k 2 2 N ∫ 0 ∞ e − x 2 2 N d x Δ 2 N ∫ 0 ∞ e − ( x 2 N ) 2 d x 2 N Δ 2 N ∫ 0 ∞ e − t 2 d t Δ 2 N π 2 Δ \begin{aligned} \sum\limits_{k0}\limits^{\infty}e^{-\frac{k^{2}}{2N}} \int_{0}^{\infty}e^{-\frac{x^{2}}{2N}}\mathrm{d}x \Delta \\ \sqrt{2N}\int_{0}^{\infty}e^{-(\frac{x}{\sqrt{2N}})^{2}}\mathrm{d}\frac{x}{\sqrt{2N}} \Delta \\ \sqrt{2N}\int_{0}^{\infty}e^{-t^{2}}\mathrm{d}t \Delta \\ \sqrt{2N}\frac{\sqrt{\pi}}{2} \Delta \\ \end{aligned} k0∑∞e−2Nk2∫0∞e−2Nx2dxΔ2N ∫0∞e−(2N x)2d2N xΔ2N ∫0∞e−t2dtΔ2N 2π Δ
由于 h ( x ) h(x) h(x) 在 x ≥ 0 x \geq 0 x≥0 上是单调递减函数 Δ ≤ ∣ h ( 0 ) − h ( ∞ ) ∣ 1 \Delta \leq |h(0) - h(\infty)| 1 Δ≤∣h(0)−h(∞)∣1于是有 ∑ k 0 ∞ e − k 2 2 N π N 2 O ( 1 ) \sum\limits_{k0}\limits^{\infty}e^{-\frac{k^{2}}{2N}} \sqrt{\frac{\pi N}{2}} O(1) k0∑∞e−2Nk22πN O(1)
上式通过欧拉-麦克劳林公式也可以导出但由于 h ( x ) h(x) h(x) 的单调性直接用积分逼近求和更简单一些。最终结果为 N 1 − ∑ k 0 N k ! k N − k N ! N − π N 2 O ( 1 ) N → ∞ N 1 - \sum\limits_{k0}\limits^{N}\frac{k!k^{N-k}}{N!} N - \sqrt{\frac{\pi N}{2}} O(1) \quad\quad N\rightarrow\infty N1−k0∑NN!k!kN−kN−2πN O(1)N→∞
也就是 N → ∞ N \rightarrow\infty N→∞ 时冒泡排序平均扫描趟数为 N − π N 2 O ( 1 ) N - \sqrt{\frac{\pi N}{2}} O(1) N−2πN O(1)。
总结
本文我们讨论了排序算法的分析中的一个问题冒泡排序平均需要跑多少趟。
首先引入了排列中的一些概念定义包括逆序、逆序表然后基于冒泡排序的算法流程发现冒泡排序扫描的趟数就是逆序表中的最大值。
再结合排列的逆序表自身的性质以及通过累积分布函数求数学期望的性质最终我们将问题归结到了 ∑ k 0 N k ! k N − k N ! \sum\limits_{k0}\limits^{N}\frac{k!k^{N-k}}{N!} k0∑NN!k!kN−k 的渐近估阶。
上式的渐近估阶非常麻烦冗长我们参考了《计算机程序设计艺术》、《算法分析导论》等名著中关于拉马努金Q函数的相关论述直接引用结果将问题转化为 ∑ k 0 ∞ e − k 2 2 N \sum\limits_{k0}\limits^{\infty}e^{-\frac{k^{2}}{2N}} k0∑∞e−2Nk2 的进行估阶。而后者通过积分逼近求和的方式或者欧拉-麦克劳林公式你可以方便解决。
最终我们得出结论 N → ∞ N \rightarrow\infty N→∞ 时冒泡排序平均扫描趟数为 N − π N 2 O ( 1 ) N - \sqrt{\frac{\pi N}{2}} O(1) N−2πN O(1)。通过这个例子我们看到使用拉马努金 Q 函数可以将某些难解的和式简化。
算法分析中使用拉马努金 Q 函数的例子非常多关于拉马努金 Q 函数的前因后果以及更多的应用后续再跟大家探讨。
