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

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

发布时间:2019-07-22 06:57 来源:未知 编辑: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,a3an排序总共有n!总结果,(其中a1=a2=a3=an)所占的概率是1/n!,每进行一次比较,就是在这n!种结果中进行二分,接着选择一个二分结果进行下一次二分,直到找到想要的排序。排序算法能不能自顶向下构造出一棵决策树?因为我们讨论的是基于输入元素的比较排序,每一次比较的返回不是0就是1,这恰好可以作为决策树的一个决策将一个事件分成两个分支。比如冒泡排序时通过比较a1和a2两个数的大小可以把序列分成a1,a2an与a2,a1an(气泡a2上升一个身位)两种不同的结果,因此比较排序也可以构造决策树。根节点代表原始序列a1,a2,a3an,所有叶子节点都是这个序列的重排(共有n!个,其中有一个就是我们排序的结果a1,a2,a3an)。如果每次比较的结果都是等概率的话(恰好划分为概率空间相等的两个事件),那么二叉树就是高度平衡的,深度至少是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的算法都是通用的

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