排序算法的O(NlogN)是什么意思(经典算法系列整理5)_第1页
排序算法的O(NlogN)是什么意思(经典算法系列整理5)_第2页
排序算法的O(NlogN)是什么意思(经典算法系列整理5)_第3页
排序算法的O(NlogN)是什么意思(经典算法系列整理5)_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、今天才搞清楚排序算法的O(N*logN)是什么意思 以前光看了n多排序算法,知道仅通过比较的排序算法一共两种复杂度O(N2)或O(N*lgN),由于高数学的不好,之前一看到后者就放弃了思考,没有真正研究为什么会有个lgN,这两天工作不是很忙,看了一下基础知识,有了一定的认识,算是初步搞清楚了原因.写在这里算是一个记录,如果有问题也请大家指正.  说到N*lgN的算法大致上有几种:堆排序,归并排序,快速排序.由于学习数据结构的时候老师讲过快速排序,(其实各种都讲过,我只记住了这种)我现在还是非常有印象的,这几种排序实际都有一个共同点,这个共同点让他们有了lgN的特性.

2、0;都是使用了分治算法,把大集合通过分治,形成小集合,小集合的排序再次递归更小集合,直到1个(还可能是2个或3个)元素为止.这样对于整个集合来讲,每次递归都是处理2个元素数量是1/2当前元素数量的新集合,f(x) = f(x/2) + a (有限极小数)这个特点在堆排序和归并排序中尤为突出,他们是绝对的遵循2分法的.而快速排序结果是随机的,如果点呗,可能出现O(N*N)的可能性 下面用堆排序为例说明一下NlgN:为了让更多人明白,我简单把堆排序说一下:堆排序就是把原来输入的值串,当成一棵完全2叉树,每次找最大值的时候,都是把数的左右子节点比较,把大于自己的最大的一个跟自己互换,找到一

3、个后,重新找剩下的n-1个,一直到最终找完所有节点.由于递归使用的是深度优先,每次都会从最底层往上找起,每次找的次数假设是F(x),则其需要找两个子树F(x/2)并且等两个子树处理完后,比较2次(子树的根比较一次,跟自己比较一次)如果连移动都算上,是3次操作值的注意的是,由于最初排列过了以后,找子树的时候只要找那颗被破坏了的子树即可,另一颗排过序了的不需要再找了. (这个我自己都感觉说的不明白,如果实在不行,大家再去看看相关资料吧)这样分析下来,找第x个节点的操作次数为: f(x) <= f(x-1)/2) +3 (当然,我理解算成 + 2也行,x-1是把根去掉)由于当x为2的整次方倍

4、+ 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

人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论