雅乐网

计算机技术、学习成长

计算机 » 算法 » 基于比较的排序算法的下界

基于比较的排序算法的下界

在排序的结果中,各个元素的次序依赖于他们之间的比较,这种排序算法叫做比较排序。基于比较的排序有O(n^2)的冒泡排序、插入排序等,也有O(nlogn)复杂度的归并排序、堆排序等。实际上,O(nlogn)在渐进意义上是最优的。

假设我们有n个元素需要排序,所有可能的情况是n个元素的全排列,共有n! 种。假设其中的两个元素时a和b,我们可以通过比较a和b这一次比较,我们可以缩小结果的范围。

下面是一个3个元素排序的决策树,来自《数据结构和算法分析c语言描述》

scrn20160108164233

树中的每个叶子节点对应了最后的结果,n个元素可能的排列有n!种,所以有n!个叶子节点。

而每个叶子结点的深度就是得到该结果所需要的比较次数。在最坏情况下,只需要考虑最深的叶子结点,数值上等于树的高度。

高度为h的二叉树,叶子结点最多有2^h个

则叶子结点n!的二叉树,高度至少是log(n!)

这也就是说,基于比较排序的复杂度下界是log(n!)

$$log(n!) = log(n*(n-1)*(n-2)* … * 3 * 2 * 1)$$

$$= log(n) + log (n-1) + log(n-2) + … + log(3) + log(2) + log(1)$$

$$\ge log(n)+ log(n-1) + … + log(n/2) $$

$$> \frac{n}{2} log(\frac{n}{2})$$

$$ = \Omega(nlogn)$$

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/sort_decision_tree.html

上一篇:

下一篇:

我要评论

验证码*: 9 + 9 =