〔算法〕排序的最低时间复杂度为什么是O（nlogn）

我刚刚学〔算法〕，不知道的多，有没有达人解释一下？

推荐答案 2008-03-13

这个首先要明确一点，只用到比较的排序算法最低时间复杂度是O(nlogn)，而像桶排这样的只需要O(R)(R为桶的大小)
为了证明只用到比较的排序算法最低时间复杂度是O(nlogn)，首先要引入决策树。
首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。
先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。
具有L片树叶的二叉树的深度至少是logL。
所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。
而
log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1
>=logn+log(n-1)+log(n-2)+...+log(n/2)
>=(n/2)log(n/2)
>=(n/2)logn-n/2
=O(nlogn)
所以只用到比较的排序算法最低时间复杂度是O(nlogn)。

温馨提示：答案为网友推荐，仅供参考

当前网址：http://33.wendadaohang.com/zd/hB4hhP0R.html

其他回答

第1个回答 2008-03-13

时间复杂度通常括号里面的是频度,就是该语句重复的次数
一般情况下只需选择一种基本操作来讨论算法的时间复杂度
nlogn就是指运行的次数
具体怎么个意思也不是太懂数学学习的不好
连logn都忘记了....

相似回答

...时间复杂度的表示法,例如 O(n²)、O(n)、O(1)、O(nlogn) 等...答：O(n)的复杂度则代表随着数据规模的线性增长，处理时间也随之增加。比如数数，从1数到100需要100秒，数到200几乎不会少于200秒，这是典型的线性增长。寻找最高分数的算法，就像逐一查看每份试卷，试卷越多，耗时越长，这就是线性时间复杂度的体现。O(n²)复杂度的算法，比如冒泡排序和选择排序，...

时间复杂度o(nlogn)的算法是什么?答：时间复杂度o(nlogn)的算法是采用“分治思想”，将要排序的数组从中间分成前后两个部分，然后对前后两个部分分别进行排序，再将排序好的两部分合并在一起，这样数组就有序。每次划分区域都选择中间点进行划分，所以递归公式可以写成：T(n) = T(n/2) + T(n/2) + n， T(1) = C(常数) //...

归并排序的时间复杂度O(n*log n)是怎么得来的,求大神详细的讲解一下答：首先你说归并排序最坏的情形为O(NlogN)，这是不正确的归并排序如果不借助辅助空间的话，复杂度为O(n^2)，借助的话就是O(nlogn)(O(nlog2n))归并排序平均复杂度是 O(nlogn) 比较快快速排序快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经...

大家正在搜

时间复杂度最低的排序算法算法的时间复杂度是指什么常见排序算法的时间复杂度算法时间复杂度排序八种排序算法时间复杂度排序算法时间复杂度总结快速排序的时间复杂度是多少各排序的时间复杂度直接选择排序的时间复杂度