冒泡排序平均需要跑多少趟:拉马努金Q函数初探

2024-02-15 13:12

本文主要是介绍冒泡排序平均需要跑多少趟:拉马努金Q函数初探,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

摘要: 拉马努金Q函数在算法分析中的应用,初步体验

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,本文我们继续来讨论算法分析中的问题。

很多数组上的算法都与 1 ∼ n 1 \sim n 1n 的排列有关,比如各种排序算法。在分析数组上的排序算法时,排列上的各种概念对分析问题很有用,比如逆序、圈、左向右最大值、上升、下降、游程、峰、谷等等。

本文我们看一下逆序的概念及其在冒泡排序的分析中的作用。然后我们解决一个相关的算法分析问题:对于 1 ∼ N 1 \sim N 1N 的随机排列, N → ∞ N \rightarrow\infty N 时,冒泡排序平均要跑多少趟。

首先给出结论, N → ∞ N \rightarrow\infty N 时,冒泡排序平均扫描趟数为 N − π N 2 + O ( 1 ) N - \sqrt{\frac{\pi N}{2}} + O(1) N2πN +O(1)

为了推导以上结论,我们首先介绍一下排列中关于逆序、逆序数、逆序表的概念。然后介绍一下冒泡排序算法的流程,然后根据逆序表的概念以及冒泡排序的流程,我们将冒泡排序平均扫描趟数问题转化为逆序表的最大值的问题。

之后我们在逆序表上经过一些组合分析,再结合数学期望的性质,将问题的答案写成了一个和式。于是原问题最终转化为了一个和式的渐近估阶的问题。

然后引用拉马努金Q函数相关的结论,对原和式化简,使得我们可以比较容易地对简化后的和式进行渐近估阶,得到最终结果。

排列的一些基本概念

p = p 1 p 2 ⋅ ⋅ ⋅ p N p = p_{1}p_{2}\cdot\cdot\cdot p_{N} p=p1p2pN 1 ∼ N 1 \sim N 1N 的一个排列。

逆序:一个逆序 i < j i < j i<j p i > p j p_{i} > p_{j} pi>pj 的一个数对。

逆序表:记 q j q_{j} qj 表示 i ∈ [ 1.. j − 1 ] i \in [1..j-1] i[1..j1] p i > p j p_{i} > p_{j} pi>pj 的个数。 q = q 1 q 2 ⋅ ⋅ ⋅ q N q = q_{1}q_{2}\cdot\cdot\cdot q_{N} q=q1q2qN 成为排列 p p p逆序表

逆序数:记 σ ( p ) = ∑ j = 1 N q j \sigma(p) = \sum\limits_{j=1}\limits^{N}q_{j} σ(p)=j=1Nqj,表示排列 p p p逆序数

排列与逆序表的一一对应

由以上定义可以知道,对于 1 ≤ j ≤ N 1 \leq j \leq N 1jN q j q_{j} qj 需要满足约束 0 ≤ q j < j 0 \leq q_{j} < j 0qj<j

给定满足该约束的任意一个序列 q = q 1 q 2 ⋅ ⋅ ⋅ q N q = q_{1}q_{2}\cdot\cdot\cdot q_{N} q=q1q2qN,下面我们构造满足该逆序表 q q q 的排列 p p p

对于 i = N , N − 1 , ⋯ , 1 i = N, N-1, \cdots, 1 i=N,N1,,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} p=p1p2pN

也就是说给定任意长为 N N N 的逆序表,至少可以构造出一个满足该逆序表的 1 ∼ N 1 \sim N 1N 的排列,下面我们说明该排列是唯一的。

由于 q i q_{i} qi 的取值范围 [ 0.. i − 1 ] [0..i-1] [0..i1] i i i 种可能,因此共有 N ! N! N! 种可能的逆序表 q = q 1 q 2 ⋅ ⋅ ⋅ q N q = q_{1}q_{2}\cdot\cdot\cdot q_{N} q=q1q2qN

另一方面我们熟知 1 ∼ N 1 \sim N 1N 的排列数为 N ! N! N!,如果在 N ! N! N! 个长为 N N N 的逆序表中,存在某个逆序表,其对应的排列不唯一,由鸽巢原理,就会出现某个 1 ∼ N 1 \sim N 1N 的排列对应两个不同的逆序表的情况,这与逆序表的定义矛盾。

因此长度为 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[i+1],则将 p [ i ] p[i] p[i] p [ i + 1 ] p[i+1] p[i+1] 交换,然后扫描下一个。否则直接扫描下一个。

如果在某趟扫描完成时,没有进行过任何交换,也就是每个元素都不比它后面的元素大,则排序就完成了。

由于每个交换都是两个相邻元素的交换,因此交换之后,逆序数减 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} q=q1q2qN 中,最大值 max ⁡ 1 ≤ j ≤ N q j \max\limits_{1\leq j \leq N} q_{j} 1jNmaxqj 的平均值是多少。

逆序表中的最大值

对于 1 ∼ N 1 \sim N 1N 的排列,给定 0 ≤ k ≤ N 0 \leq k \leq N 0kN,考察所有项都小于 k k k 的逆序表的个数。

考察 q i q_{i} qi。如果 i ≤ k i \leq k ik q i q_{i} qi 可以取 [ 0.. i − 1 ] [0..i-1] [0..i1] 的任意值。当 i > k i > k i>k 时, q i q_{i} qi 可以取 [ 0.. k − 1 ] [0..k-1] [0..k1] 之间的值。

于是 N ! N! N! 种长为 N N N 的逆序表中,所有项都小于 k k k,也就是最大项小于 k k k 的逆序表的个数为 k ! k N − k k!k^{N-k} k!kNk

因此 N ! N! N! 个长为 N 的逆序表中,最大项大于等于 k k k 的概率为 1 − k ! k N − k N ! 1 - \frac{k!k^{N-k}}{N!} 1N!k!kNk

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(Qk)=1N!k!kNk

下面我们要求 E [ Q ] E[Q] E[Q]。这需要用到通过累积分布函数求数学期望的性质。

由累计分布函数求数学期望

我们知道,根据定义计算数学期望的一般方法如下。

X X X 为离散型,分布律为 P ( X = x ) P(X=x) P(X=x)

E [ X ] = ∑ x x P ( X = x ) E[X] = \sum\limits_{x}xP(X=x) E[X]=xxP(X=x)

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(Xn),那么有:

E [ X ] = ∑ n = 0 ∞ P ( X ≥ n ) E[X] = \sum\limits_{n=0}\limits^{\infty}P(X\geq n) E[X]=n=0P(Xn)

证明

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_{x=0}\limits^{\infty}xP(X=x) \\ &= \sum\limits_{x=0}\limits^{\infty}\sum\limits_{n=0}\limits^{x}P(X=x) \\ &= \sum\limits_{n=0}\limits^{\infty}\sum\limits_{x=n}\limits^{\infty}P(X=x) \\ &= \sum\limits_{n=0}\limits^{\infty}P(X\geq x) \\ \end{aligned} E[X]=x=0xP(X=x)=x=0n=0xP(X=x)=n=0x=nP(X=x)=n=0P(Xx)

□ \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(1F(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]=0yf(y)dy=00yf(y)dxdy=0xf(y)dydx=0(1F(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_{k=0}\limits^{N}(1 - \frac{k!k^{N-k}}{N!}) = N + 1 - \sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!} k=0N(1N!k!kNk)=N+1k=0NN!k!kNk

于是最初的问题最终归结到了对 ∑ k = 0 N k ! k N − k N ! \sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!} k=0NN!k!kNk 的渐近估阶。

对以上和式做下标变换:

∑ k = 0 N k ! k N − k N ! = ∑ k = 0 N ( N − k ) ! ( N − k ) k N ! \sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!} = \sum\limits_{k=0}\limits^{N}\frac{(N-k)!(N-k)^{k}}{N!} \\ k=0NN!k!kNk=k=0NN!(Nk)!(Nk)k

f N ( k ) = ( N − k ) ! ( N − k ) k N ! f_{N}(k) = \frac{(N-k)!(N-k)^{k}}{N!} fN(k)=N!(Nk)!(Nk)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-k+1} \\ &= (1 - \frac{k}{N})\cdot (1 - \frac{k-1}{N-1}) \cdot\cdot\cdot (1 - \frac{1}{N-k+1}) \\ &= \prod\limits_{i=1}\limits^{k}(1 - \frac{i}{N-k+i}) \\ \end{aligned} fN(k)=N!(Nk)!(Nk)k=NNkN1NkNk+1Nk=(1Nk)(1N1k1)(1Nk+11)=i=1k(1Nk+ii)

后续的处理非常复杂,需要对 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_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!} = \sum\limits_{k=0}\limits^{N}f_{N}(k) = \sum\limits_{k=0}\limits^{N}e^{-\frac{k^{2}}{2N}} + O(1) \quad\quad N\rightarrow\infty k=0NN!k!kNk=k=0NfN(k)=k=0Ne2Nk2+O(1)N

以后有时间可以再回来看一下上式的推导过程,感兴趣的可以看《算法分析导论》或《计算机程序设计艺术》中关于拉马努金Q函数的内容。

积分逼近求和

下面对 ∑ k = 0 ∞ e − k 2 2 N \sum\limits_{k=0}\limits^{\infty}e^{-\frac{k^{2}}{2N}} k=0e2Nk2 进行估阶。记 h ( x ) = e − x 2 2 N h(x) = e^{-\frac{x^{2}}{2N}} h(x)=e2Nx2。可以用积分逼近求和:

∑ 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_{k=0}\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} k=0e2Nk2=0e2Nx2dx+Δ=2N 0e(2N x)2d2N x+Δ=2N 0et2dt+Δ=2N 2π +Δ

由于 h ( x ) h(x) h(x) x ≥ 0 x \geq 0 x0 上是单调递减函数, Δ ≤ ∣ 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_{k=0}\limits^{\infty}e^{-\frac{k^{2}}{2N}} = \sqrt{\frac{\pi N}{2}} + O(1) k=0e2Nk2=2π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_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!} = N - \sqrt{\frac{\pi N}{2}} + O(1) \quad\quad N\rightarrow\infty N+1k=0NN!k!kNk=N2πN +O(1)N

也就是, N → ∞ N \rightarrow\infty N 时,冒泡排序平均扫描趟数为 N − π N 2 + O ( 1 ) N - \sqrt{\frac{\pi N}{2}} + O(1) N2πN +O(1)

总结

本文我们讨论了排序算法的分析中的一个问题:冒泡排序平均需要跑多少趟。

首先引入了排列中的一些概念定义,包括逆序、逆序表,然后基于冒泡排序的算法流程,发现冒泡排序扫描的趟数就是逆序表中的最大值。

再结合排列的逆序表自身的性质,以及通过累积分布函数求数学期望的性质,最终我们将问题归结到了 ∑ k = 0 N k ! k N − k N ! \sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!} k=0NN!k!kNk 的渐近估阶。

上式的渐近估阶非常麻烦冗长,我们参考了《计算机程序设计艺术》、《算法分析导论》等名著中关于拉马努金Q函数的相关论述,直接引用结果,将问题转化为 ∑ k = 0 ∞ e − k 2 2 N \sum\limits_{k=0}\limits^{\infty}e^{-\frac{k^{2}}{2N}} k=0e2Nk2 的进行估阶。而后者通过积分逼近求和的方式或者欧拉-麦克劳林公式你可以方便解决。

最终我们得出结论, N → ∞ N \rightarrow\infty N 时,冒泡排序平均扫描趟数为 N − π N 2 + O ( 1 ) N - \sqrt{\frac{\pi N}{2}} + O(1) N2πN +O(1)。通过这个例子我们看到,使用拉马努金 Q 函数可以将某些难解的和式简化。

算法分析中使用拉马努金 Q 函数的例子非常多,关于拉马努金 Q 函数的前因后果,以及更多的应用,后续再跟大家探讨。

这篇关于冒泡排序平均需要跑多少趟:拉马努金Q函数初探的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/711484

相关文章

Kotlin 作用域函数apply、let、run、with、also使用指南

《Kotlin作用域函数apply、let、run、with、also使用指南》在Kotlin开发中,作用域函数(ScopeFunctions)是一组能让代码更简洁、更函数式的高阶函数,本文将... 目录一、引言:为什么需要作用域函数?二、作用域函China编程数详解1. apply:对象配置的 “流式构建器”最

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

kotlin的函数forEach示例详解

《kotlin的函数forEach示例详解》在Kotlin中,forEach是一个高阶函数,用于遍历集合中的每个元素并对其执行指定的操作,它的核心特点是简洁、函数式,适用于需要遍历集合且无需返回值的场... 目录一、基本用法1️⃣ 遍历集合2️⃣ 遍历数组3️⃣ 遍历 Map二、与 for 循环的区别三、高

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

golang panic 函数用法示例详解

《golangpanic函数用法示例详解》在Go语言中,panic用于触发不可恢复的错误,终止函数执行并逐层向上触发defer,最终若未被recover捕获,程序会崩溃,recover用于在def... 目录1. panic 的作用2. 基本用法3. recover 的使用规则4. 错误处理建议5. 常见错