基于比较排序的算法复杂度的下界-白红宇

基于比较排序的算法复杂度的下界

阅读量：4352 次

发布时间：2019-06-07

本文共 409 字，大约阅读时间需要 1 分钟。

2019-04-28 20:51:54

首先，所有基于比较的排序算法，都是以决策树模型作为依据的。

对于待排序的

n 个元素，其所有可能的排序种数为 n! ，其决策树高度为h （即为排序算法比较的次数）

高度为 h 的决策树，最多有叶子节点

$2^{h}$ 个，所以就有

$2^{h}>=n!$

$h>=log(n!)$

由斯特林近似公式：

$n!=\sqrt{2\pi n} *(\frac{n}{e} )^{n}*(1+\Theta (\frac{1}{n} ))$

得

$h>=\frac{1}{2} log(2\pi)+\frac{1}{2}log(n)+nlog(n)-nlog(e)+log(1+\Theta (\frac{1}{n}))$

其中，

$\Theta (\frac{1}{n} )\in \left[ e^{\frac{1}{12n+1} } \,,e^{\frac{1}{12n}} \right]$

故，

$h$ 的渐近下界为

$\Omega (nlog(n))$

【补充】

如果不使用斯特林公式，依然可以证明得到log(n!)和nlogn是同阶的。

1）显然的是n! < n^n，因此log(n!) < nlogn

2) n! = n * (n - 1) * ... * 1, 我们可以将前n / 2的数字放缩到n / 2，后面的所有数字舍去，因此n! > (n / 2) ^ (n / 2)，得log(n!) > nlog(n)

综上，logn! 和 nlogn是同阶的。

转载于:https://www.cnblogs.com/TIMHY/p/10786592.html

你可能感兴趣的文章

C++基础--完善Socket C/S ，实现客户端，服务器端断开重连

linux中shell变量$#,$@,$0,$1,$2的含义解释

查看>>

常用的shell命令整理

查看>>

A Brief Introduction to the Design of UBIFS

查看>>

了解你的Linux系统：必须掌握的20个命令

查看>>

js setInterval 启用&停止

查看>>

knockoutJS学习笔记04：监控属性

ASP.net Web窗体添加多条数据到数据库

查看>>

PHP面向对象（三）

查看>>