您好、欢迎来到现金彩票网!
当前位置:PC蛋蛋 > 最优归并树 >

基于比较的排序算法的最优下界为什么是O(nlogn)

发布时间:2019-07-25 20:30 来源:未知 编辑:admin

  回答这个问题之前我们先来玩一个猜数字的游戏,我从1到8中挑一个数字出来让你来猜,每回合你都可以问我一个问题,我的回答“是”或“不是”(1或0),那么你至少需要几个回合才能保证猜出这个数字?比较符合这个游戏精神的玩法是从自己的幸运数字(比如我的是7)开始猜起,一个一个地问我“是不是X?”,可能你的运气足够好,一个回合就能够猜对,但是在最坏的情况下可能就需要8个回合,所以你的答案应该是“至少需要8个回合”(事实上你至少只需要一次就“有可能”猜出来,但为了“保证能”猜出来,你只好委曲求全地说8),换句话说这种猜法的最优下界是8。(平均性能是1×1/8+2×1/8+…+8×1/8=(1+…8)/8=4.5)

  但因为你会二分,所以会这样问“是不是比4大?”……而且无论我挑出的数字是几,都只用3个回合。显然这是一种更佳的策略,那么它好在什么地方呢?

  如果用信息论的思想来解释,这种猜法每一轮(提问并得到反馈)得到的信息量更大。因为在你不知道这个问题的答案时,我回答“是”和“不是”的概率是相同的(如果你不打开盖子,猫是死还是活的概率是相同的),因此每回合你所获取的信息量都是最大的(熵)。而第一种猜法,比方你第一次问我“是不是7?”,我回答“不是”的概率为“是”的概率的7倍(1/8:7/8),因此得到的信息量就少了。如果你问我“是不是42?”那么信息量就更少了(为0),因为我回答“是”的概率为0……相当于你这个问题白问了。

  这就像一个未知的世界,一开始你对这个世界一无所知,然后你通过问我问题来获取一些信息,直到你所取得的信息量能够帮助你认清这个世界。

  另一种更加形象的模型是决策树(如图),每一个决策都将引出两个结果,叶子节点代表数字已经猜出。二分思想的决策树十分平衡,因此每次猜测无论是对还是错都能将够将数字的范围缩小一半。最优下界即二叉树的深度,具有L片树叶的二叉树的深度至少是logL,所以logn是n个数字的最优下界。而下面那棵二叉树,虽然很有可能在在第一次分支处就使游戏终结,但是却有很大的概率会失败(需要接着往下猜),这个时候回过头来看刚刚的决策——仅仅将范围缩小了一点点。从直观上感觉这种方法也是比较冒风险的。

  绕了一个大圈子其实就是为了说比较排序的决策树模型。a1,a2,a3……an排序总共有n!总结果,(其中a1=a2=a3……=an)所占的概率是1/n!,每进行一次比较,就是在这n!种结果中进行二分,接着选择一个二分结果进行下一次二分,直到找到想要的排序。排序算法能不能自顶向下构造出一棵决策树?因为我们讨论的是基于输入元素的比较排序,每一次比较的返回不是0就是1,这恰好可以作为决策树的一个决策将一个事件分成两个分支。比如冒泡排序时通过比较a1和a2两个数的大小可以把序列分成a1,a2……an与a2,a1……an(气泡a2上升一个身位)两种不同的结果,因此比较排序也可以构造决策树。根节点代表原始序列a1,a2,a3……an,所有叶子节点都是这个序列的重排(共有n!个,其中有一个就是我们排序的结果a1,a2,a3……an)。如果每次比较的结果都是等概率的话(恰好划分为概率空间相等的两个事件),那么二叉树就是高度平衡的,深度至少是log(n!)。又因为log(n!)的增长速度与 nlogn 相同,即 log(n!)=Θ(nlogn),这就是通用排序算法的最低时间复杂度O(nlogn)的依据。

  为了理解O(nlogn)这个公式的含义,下面来看这样一道题:排序5个数至少需要几次比较?

  用合并排序(merge sort,算法复杂度为O(nlogn))对3、2、5、1、4进行排序。下面给出了5个数合并排序的归并树,共需要4+2+1+1=8次比较。

  那么,这是最优的吗?通过决策树模型,我们知道基于比较的排序算法的算法复杂度是log(n!),因此排序5个数所需要最小的比较次数应该是7次(log(5!)=log(120)≈6.91),而归并排序用了8次。

  虽然log(n!)和nlogn的增长率相同,但在n比较小的时候,后者的值差不多是前者的两倍。(下表是这函数的增长规律,log(n!)比较难计算,用chromey calculator最多只能算到log(170!))。

  如果我们用nlogn这个公式计算5数归并排序的算法复杂度,得到的结果应该是12,事实上只需要8次比较即可。原因是在用“递归树”(算法导论p22)计算merge sort的算法复杂度的时候,我们保守估计了每层的复杂度,n是已经是一个上界了,换句话说每层是O(n),有logn+1层,因此归并算法的最优下界是O(nlogn)。

  实际的使用归并算法排n数的复杂度总是要低于nlogn(因为每层比较次数少于n)的,能否等于log(n!)(最优的下界)呢?不可能,反例就是n=5,(证明一个东西错误总是比证明它正确容易得多——Knuth),那么为什么不行呢?还是那个老问题,看它对于事件的划分。虽然我没有画出5数归并排序的决策树,但是从归并树上也可以看出问题出在“ [2][3][5](2次)”的这一步。这一步有两次比较:第一次比较2和5,较小的数字进入a[0];第二次将较大的那个数和3进行比较,较小的进入a[1],较大的进入a[2]。而在第一次比较时就出现了概率不均的场面,如果52将产生[5][2][3]这一种结果,反之将得到[2][5][3]和[2][3][5]两种结果,概率空间1:2!

  下图给出了用7次排5数的决策树(如果对称则省去一支),可以看到每次划分都是十分均衡的。

  划分的关键是第三、第四次比较,“a与b”和“c与d”的那比较肯定是等概率的,如果之后分别将e与a和b(或者c和d)比较,将会使两个分支出现一大一小的场面,在比较的初期,出现这种不平衡是致命的!一个分支可能提前“解放”,经过三两次二分就得到了结果,另一个分支的“责任”则突然变大,导致无法再指定次数内完成分解。

  唯一的不均衡出现在第5层,因为15不能被2整除,所以7:8已经算得上是很不错的划分了。所以只有在n!=2^k时,才有可能出现一棵高度平衡的二叉树。

  因此这个排序算法的最优下界好于merge sort,缺点是只能排5数,因此这个算法不是通用算法,而诸如归并、快排、堆排、希尔在内的最优下界为nlogn的算法都是通用的。

  这个首先要明确一点,只用到比较的排序算法最低时间复杂度是O(nlogn),而像桶排这样的只需要O(R)(R为桶的大小)为了证明只用到比较的排序算法最低时间复杂度是O(nlogn),首先要引入决策树。首...博文来自:micx0124的专栏

  快排的O(NlogN)真的最快了吗?相信大家都已经知道如归并排序、快速排序等算法能在把排序的时间复杂度降为O(NlogN)级别,而排序的时间复杂度理论上最好是O(N)级别,因为最优情况也得把数据读取一...博文来自:isjinhao的博客

  基于比较的的排序的下界问题的提出前面我们我们讨论的了从O(n2n2n^2)到O(n*lgn)的排序方法.这些排序方法都一个共同点:它们只能依赖元素的比较来判断其顺序,或者换一种说法是仅仅是依靠比较来进...博文来自:遇见你真好

  前言      之前在查找基于比较排序算法的时间复杂度时发现,好多博主对“最坏”下界与“最优”下界没有分清,而是默认的把时间复杂度o(nlogn)当成了“最优”下界。这样很是误导大家,影响很不好。所以...博文来自:WFL_Tesla的博客

  这是一个证明基于比较的排序算法的时间复杂度为何为nlgn(ps:在计算机学科中所有的lg表示log2)对于每个比较排序算法都可以用一颗决策树表示决策树,基于不同的情况出现不同的答案还记得小时候学过的那...博文来自:permi_yaxileni的博客

  最近在看rudin的数学分析原理,1.11里面有证明最小下界性的问题不明白, 如果 ∞ 序列S 为 ∑1/n n=1 ∞ 序列B 为 ∑1/n n=2 B 是 S 的线, 满足最论坛

  快过年了,回家了,发个非技术博客吧。最近被百家号恶心到不行,搜了下屏蔽方法,在家懒得翻墙用谷歌,又懒得装插件设置屏蔽,找到了一个简单有效的方法,直接在搜索内容后边加-(baijiahao),效果还不错...博文来自:慢慢积累

  这是在接触一段时间的Linux网络通信后回过来给自己重新熟悉一些基本函数功能,所以,这里不做任何代码注释,自己慢慢去查看每一个函数的原型、参数含义、返回值以及调用方式,这样才能真正学到东...博文来自:逸璞丷昊的博客

  定时器是我们需要经常处理的一种资源。那linux下面的定时器又是怎么一回事呢?其实,在linux里面有一种进程中信息传递的方法,那就是信号。这里的定时器就相当于系统每隔一段时间给进程发一个定时信号,我...博文来自:weixin_34347651的博客

  电脑配置:1,双硬盘:SSD120G+HDD500G;2,电脑没有EFI模式,只能用GRUB模式;3,电脑boot只能识别主硬盘位的SSD,光驱位HHD开机时不识别;(导致按教程安装不成功,折腾了三天...博文来自:独钓寒江雪

  本文将主要说明Ajax与Action数据交互的实现过程,前端使用JQuery中Ajax的相关方法,get或者post,将数据以Json格式传回到业务调度Action中,Action中处理后,再讲数据以...博文来自:正在加载中

  1引言目前深度学习模型已经应用到了各个领域,将TensorFlow训练模型部署到终端上也逐步变为了现实。特别是mobileNet等体积小,占用内存少的模型出现后,将深度学习应用到终端上逐渐变得火热起来...博文来自:谢杨易的博客

  刚刚换了固态硬盘,替换下来的机械硬盘,买了移动硬盘盒,组装成了移动硬盘,但是,因为这个硬盘之前在我的电脑里设置过,插上后是动态的,磁盘管理识别无效。百度一番,说是要备份后,在磁盘管理中转换为基本磁盘,...博文来自:不努力的人不配谈理想

  线、线路交换进行通信:是指在两个站之间有一个实际的物理连接,这种连接是结点之间线、线路通信三种状态:线路建立、数据传送、线、线路交换缺点:典型的用户/主机数据连接状态,...博文来自:华农老林的博客

  .net framework 能否打包到安装程序里面? 如何没有安装,系统帮自动安装. 有没相关的例子代码?论坛

  最近在工作中遇到一个问题,发现直接用集合去接收前台传过来的集合,会报如下图的错然后百度了很多种方法,百度的过程中看到的有比如在接收的参数前面加入@RequestBody但是我试过之后好像没什么用也有说...博文来自:weixin_43009990的博客

  我是域用户,我写了一个PowerShell脚本,查询某个文件夹下的文件数,并记录到文件中。 运行这个PowerShell脚本,结果正常。现在把这个脚本加到“任务计划”中自动执行,我发现只有当我在任务计论坛

  测试程序时候发现在pycharm中同一目录执行f=open(“1.txt”)找不到文件,但是在命令行中正常,第一反应肯定是pycharm哪里没设置对,设置了半天sourceroot之类的还不行,然后把...博文来自:wangjinyu124419的博客

  (请直接看最后一个最新的,激活码在后面!!!转载的请附上原文链接搜索不易!)失效后请重新复制最新激活码目录失效后请重新复制最新激活码当前最新激活码为:2019.07.16注册码2018.10.01注册...

  今天使用eclipse时卡死了,再打开出现了这个错误(anerrorhasoccurredseethelogfile)。没办法,自己上网找了很多方法,总算是解决掉了。这里,我总结了一下解决这个问题所用...

  write()系列方法进行写操作时并不一定直接将所写的内容写出,而先将需要写出的内容放到输出缓冲区,知道缓冲去满、调用flush()方法刷新流或调用close()方法关闭流时才真正输出。这样处理可以减...

  “工具善其事,必先利其器!装好这些插件让vs更上一层楼” ReSharper : 首先的是Resharper,这个基本是目前是我开发过程中必备的工具集,唯一的缺点就是吃内存,所以你的内存要是低于8G,...

  今天测试项目时发现页面有些数据乱码了,检查了一下发现数据存入redis还是中文,取出来就乱码了TT代码:...

  在做设备软件的时候,需要调用我司服务器的数据,就是用远程接口调用。这里没有直接用socket,网上的一些案例只是简单地额实现。在实际开发中,经常是url路径的整体调用。此时对于那些有参数的传递的url...

  在上一篇[.netcore项目实战之基于RestfulAPI+Swagger项目搭建]主要介绍了项目WebApi的基本搭建,本篇主要针对开发过程中一些常用的操作方法配置读取.netcore下读取配置还...

  1.主要贡献2.元学习2.1用于跟踪的元学习2.具体应用1.主要贡献这篇文章是ECCV18的文章,不是一个单独的跟踪算法而是一种用于增强基于DNN跟踪算法性能的方法。下面就来说一下这篇文章吧,有不对的...

  数字信号处理课程中基于matlab的低通滤波器的设计1.实验要求在Matlab中绘制以下信号:x(t)=sin(20pit)+sin(200pit);要求:采样频率是信号上限频率的4-6倍或更高,绘制...

  本教程来至站本实验类似第二节蜂鸣器发声的程序,没有光照时,正常发出声音,但声音特别的小;当有光照时,光敏电阻的阻值减小,所以蜂鸣器两端的电压就会增大,蜂鸣器声音更大。光照越...

  零写在前面一有哪些技术可以做表单验证二注册界面实现1效果图2在head标签中引入样式表3在body标签中写出界面4js文件引入三js表单验证实现1定义提示框显示内容2对输入框样式进行控制3对用户名进行...

  本文对Openflow的发展、规范、应用和SDN的提出及相关应用做出较为客观全面的介绍。笔者希望通过本文对OpenFlow/SDN做一个初步介绍,以期帮助大家能够进一步深入了解和学习OpenFlow/...

  乘风丶破浪的博客Adobe CC 2019通用破解工具和破解补丁使用教程

  由于我昨天收到了Adobe软件PR和AEM的更新导致无法破解,所以我找到了一款可以离线软件的激活工具—GenP.原版的GenP有五张图片不太好认识,所以我自己添加了制作的图片,这...

  WFL_Tesla:说实话,楼主你的理解是错误的,这篇文章真的有点误人子弟。 第一,基于比较的排序算法的最坏情况下界是O(nlogn)(请注意,是最坏情况下)。 第二,基于比较的排序算法的最好情况下界是O(n)(从决策树到叶节点最短距离就是n次比较)。 第三,楼主所举例的5个数比较次数突破了最坏下界O(nlogn),这个说法不严谨。因为最坏下界严格来说是O(log(n!)),斯特林公式表示只有在n很大时才基本等于O(nlogn),n=5明显不是一个很大的数,真实最坏下界的确为log(5!)≈7。 这些在算法导论8.1节“排序算法下界”都有讲的。 最后,说话有些直接,冒犯之处还请见谅(๑*[表情]*๑)

http://cairowatch.com/zuiyouguibingshu/134.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有