聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

[原]归并排序,快速排序为什么快

2021-11-20 09:14 浏览: 3407080 次 我要评论(0 条) 字号:

对于一个nnn个元素的数组,必须要确定两两之间的相对顺序,假设每次都抓取不同的二元组,需要log⁡2n!log_2n!log2​n!次比较,由于log⁡2n!≈nlog⁡2nlog_2n!approx nlog_2nlog2​n!≈nlog2​n,O(nlog⁡2n)O(nlog_2n)O(nlog2​n)就是排序算法的下界。 前面几周写过一篇散文: https://zhuanlan.zhihu.com/p/429710417 但紧接着问题就来了,到底为什么归并排序,快速排序快呢? 这里有必要澄清

作者:dog250 发表于 2021/11/20 08:07:36 原文链接 http://it.taocms.org/11/93396.htm
阅读:0


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复