文档章节

今天才搞清楚排序算法的O(N*logN)是什么意思

徐学良
 徐学良
发布于 2017/03/25 10:02
字数 955
阅读 482
收藏 0

以前光看了n多排序算法,知道仅通过比较的排序算法一共两种复杂度

O(N2)或O(N*lgN),

由于高数学的不好,之前一看到后者就放弃了思考,没有真正研究为什么会有个lgN,

这两天工作不是很忙,看了一下基础知识,有了一定的认识,算是初步搞清楚了原因.

写在这里算是一个记录,如果有问题也请大家指正.

 

 

说到N*lgN的算法大致上有几种:堆排序,归并排序,快速排序.

由于学习数据结构的时候老师讲过快速排序,(其实各种都讲过,我只记住了这种)我现在还是非常有印象的,

这几种排序实际都有一个共同点,这个共同点让他们有了lgN的特性.

 

都是使用了分治算法,把大集合通过分治,形成小集合,小集合的排序再次递归更小集合,直到1个(还可能是2个或3个)元素为止.

这样对于整个集合来讲,每次递归都是处理2个元素数量是1/2当前元素数量的新集合,

f(x) = f(x/2) + a (有限极小数)

这个特点在堆排序和归并排序中尤为突出,他们是绝对的遵循2分法的.而快速排序结果是随机的,如果点背,可能出现O(N*N)的可能性

 

下面用堆排序为例说明一下NlgN:

 

为了让更多人明白,我简单把堆排序说一下:

堆排序就是把原来输入的值串,当成一棵完全2叉树,每次找最大值的时候,都是把数的左右子节点比较,把大于自己的最大的一个跟自己互换,找到一个后,重新找剩下的n-1个,一直到最终找完所有节点.

由于递归使用的是深度优先,每次都会从最底层往上找起,每次找的次数假设是F(x),则其需要找两个子树F(x/2)并且等两个子树处理完后,比较2次(子树的根比较一次,跟自己比较一次)如果连移动都算上,是3次操作

值的注意的是,由于最初排列过了以后,找子树的时候只要找那颗被破坏了的子树即可,

另一颗排过序了的不需要再找了. (这个我自己都感觉说的不明白,如果实在不行,大家再去看看相关资料吧)

这样分析下来,找第x个节点的操作次数为: f(x) <= f((x-1)/2) +3 (当然,我理解算成 + 2也行,x-1是把根去掉)

由于当x为2的整次方倍 + 1 的时候,正好是这个数值,当其他的情况 也不大于这个值

所以我们可以就使用最大值的情况 f(x) = f((x-1)/2) + 3; 为了计算更容易

直接 f(x) = f(x/2) + 3

 f(x/2) = f(x/4) + 3

......

 f(x/2m-1) = f(x/2m) + 3   (2m>=x)  <= f(1)+3 < 3;

由于一共m个算式 加起来是 f(x) = 3m 而 m = log(2)(x)

f(x)=3log(2)(x);

而计算f(1)+f(2) + ... + f(n)的时候,我们把他分城 m段(m= log(2)(n)) (分别为1,2,4,8,...2m-1)个元素(当然最后一端可能没有那么多)

求他们的和的话就是

2m-1(m-1) + 2m-2(m-2) + ....<2m-1m + 2m-2m + ... < 2mm 而m = log(2)(N)

 2mm =  2log(2)(n)*log(2)(n) = N * log(2)(N)

得证 哈哈

 

总之一句话:

2^n = N 则 n = log以2为底N的对数,程序中写为logN

本文转载自:http://blog.csdn.net/coollangzi/article/details/6016041

徐学良
粉丝 24
博文 213
码字总数 13841
作品 0
浦东
程序员
私信 提问
常见排序算法小结

http://blog.csdn.net/whuslei/article/details/6442755 排序算法经过了很长时间的演变,产生了很多种不同的方法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都有它特...

毛朱
2015/09/11
31
0
Python中六大排序算法与代码实现

排序 排序算法是一种能将一串数据按照特定顺序进行排序的一种算法 排序算法的稳定性 稳定排序算法就让原本有相等键值的记录维持相对次序。 就是在第一排序之后,次序与原来顺序保持一致的就是...

u012193416
2017/12/13
0
0
比较排序算法

比较排序算法分类 比较排序(Comparison Sort)通过对数组中的元素进行比较来实现排序。 比较排序算法(Comparison Sorts) Category Name Best Average Worst Memory Stability 插入排序 (...

嗯哼9925
2017/12/06
0
0
前端笔试&面试爬坑系列---算法

终于来了,算法相关的。 其实个人理解,前端岗位对于算法的要求与其他IT岗位相比,是低得多的。 但是小白我经历了如蚂蚁金服、网易这样的大厂教做人之后,还是觉得,对于一些基本算法、思想的...

Vincent Ko
2018/08/15
0
0
排序算法C语言实现——冒泡、快排、堆排对比

对冒泡、快排、堆排这3个算法做了验证,结果分析如下: 一、结果分析 时间消耗:快排 < 堆排 < 冒泡。 空间消耗:冒泡O(1) = 堆排O(1) < 快排O(logn)~O(n) 。 应用推荐:   1、速度最快、且...

Jo_ZSM
2018/10/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

读书replay《maven实战》.1.20190526

前情提要 maven这个工具用了好久了,但是一直都用的迷迷糊糊的,没有对它进行过系统性的学习,只是知道一些常用的功能怎么实现,所以20190516这一天我从JD购买了徐晓斌老师所著的《maven实战...

wanxiangming
31分钟前
0
0
真实项目案例实战——【状态设计模式】使用场景

什么是状态模式 状态模式允许一个对象在其内部状态改变的时候改变其行为。这个对象看上去就像是改变了它的类一样。 状态模式应用场景 1.一个对象的行为取决于它的状态,并且它必须在运行时刻根...

须臾之余
38分钟前
0
0
Java 实现把字符串转换成整数【底层实现】

https://blog.csdn.net/zl18310999566/article/details/80263396

qimh
41分钟前
0
0
IDEA的debugger

1、win下节省内存空间 3、条件断点

一只小青蛙
52分钟前
3
0
炸!亿级数据DB秒级平滑扩容

一步一步,娓娓道来。 一般来说,并发量大,吞吐量大的互联网分层架构是怎么样的? 数据库上层都有一个微服务,服务层记录“业务库”与“数据库实例配置”的映射关系,通过数据库连接池向数据...

编程SHA
58分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部