Quicksort,需要
heapsort,需要
merge sort,需要
insertion sort,需要
在前几天的时间我们看到了这一些演算法,我们发现他们最快时间都在,那有没有可能有一个演算法它的速度是快过於的?
我们会发现这上面四种排序的演算法都有一个性质,就是透过比较两个元素的大小关系来做出排序,也就是它们是基於同样的一种演算法模型去设计的演算法,而在这个演算法模型底下,是我们能够达到的最快速度。
在这个演算法模型中,规范了我们能够对两个元素a和b进行怎样的操作,像是我们可以执行, , , , 这些操作,如果我们对整数集合进行排序,我们只能对元素进行比较的操作,不能做出相加,相乘等等在这个演算法模型规范以外的操作。
关於透过比较方式进行的排序,我们可以使用决策树来表示他,决策树是一颗完全二元树,他可以表示给定固定大小的输入,产生出所有可能排序情况。
假设给定阵列
从树根开始看,比较和,
如果,就和进行比较。
如果,就和进行比较。
给定阵列,我们想要产生出由小到大的排列,整个决策树的走法如下
最终产生出的组合为(3,1,2),即为由小到大的排列方式。
在决策树中,每一个内部节点都是以标记,其中,维阵列中元素的个数。每个内部节点会分出两颗子树,左子树表示所需要进行的後续比较,右子树表示所需要进行的後续比较。对於一个正确的比较排序演算法,个元素的阵列会产生出种排列的情况,也就是产生出个叶节点。
上面提及的四种演算法都可以使用决策树的方式进行表示,但一般来说不会那麽做,原因为考虑一般性,也就是考虑排序长度为的阵列,会有个节点,导致树长的非常大一棵,因此一般描述演算法时会采用虚拟码的方式进行描述。
使用决策树的好处,在於我们可以直观的分析对於长度为的阵列,排序所需要的执行时间与最差情况。
从树根到任一叶节点之间的路径长度,表示排序演算法所需要进行比较的次数,也就是执行时间,可以表示成树的深度。而最坏情况就是树根到叶节点最长的路径长度,也就是树的高度,有最多的比较次数。
我们要证明在这个比较模型底下,没有任何一种演算法是要比还要快的,也就是最长路径的最小值为
证明: 对於长度为n的阵列所绘制出的决策树,其树高为
对於长度为n的阵列所绘制出的决策树,其拥有个节点,令决策树的高度为,叶子数量为,则最多拥有个叶节点,因为这是一棵二元树,每个节点都有两个分支,因此我们可以得出下面关系式
,对两边式子取对数
(因为为单调递增函数,因此可以做这样的操作)
根据Stirling's formula,用来取的近似值
,和为常数,当n趋近於无限时可以忽略不计
结论: 对於使用比较大小方式进行排序的演算法,皆可以对应到决策树,并且效率都不会好过於,而heapsort,merge sort和随机化的quicksort他们执行时间的上界为,恰好对应到决策树的下界。随着n的增长,heapsort,merge sort随机化的quicksort会渐进式的趋近於在决策树模型下的最优解,也就是贴近他的下界。
线性时间几乎是我们可以得到的最有效率结果(不考虑平行化处理或是一些情况),因为我们至少需要遍历过整个数据。
如何在线性时间内完成排序,要突破模型的限制,就是我们不在比较元素的大小,对元素做其他的操作,也就是让这个演算法不被这个模型所包含,那这个演算法就有机会达到线性时间内的排序了。
参考资料:Introduction to algorithms 3rd
<<: Day8. 依点成形,创造物件 - RigidBody(下)
>>: Day-22 创新才是正义!带领任天堂重返荣耀的 Wii
Hi 这里是小将,这次铁人赛拖了一阵子才终於参赛了,老样子,还是没囤稿,就来看看这三十天究竟能玩出甚...
摘要 导入套件 模型初始化资料 API初始化 server_uuid 转换图片格式 模型辨识手写中文...
应该是延续 php 的漏洞问题... 18. Cereal hacker2 Points: 500 ...
一、究竟AI能不能预测股价? 不能 好了,被我骗进来的可以按上一页了(X 结论已经讲了,如果你对原因...
开始前的构思: 在这次动手做实验前,试着构思了一个透过云端提供的工具让服务持续演进的想法,左思右想考...