代码之家 › 专栏 › 技术社区 › Aaron Fi

谁首先证明了所有基于比较的排序都是Ω(n lgn)?

sorting algorithm

Aaron Fi · 技术社区 · 14 年前

这个下限上有名字吗?e、 SomeGuysLastName定理?

2 回复 | 直到 14 年前

matt 14 年前

我的《算法导论》副本在第8章的注释中有这样的内容,这就是讨论这个界限的地方:

Ford和Johnson(1)提出了研究比较排序的决策树模型。Knuth关于排序(2)的全面论述涵盖了排序问题的许多变化,包括这里给出的排序复杂性的信息论下界。

(1) 小雷斯特·R·福特和塞尔默·M·约翰逊。比赛的问题。 美国数学月刊 ,66:387-3891959年。

排序和搜索 ,第3卷,共 . 艾迪生·韦斯利,1973年。

不是对你问题的明确回答,但它是有意义的。

Harmen 14 年前

但也许公元前400年希腊人证明了这一点,这真的重要吗?

http://en.wikipedia.org/wiki/Merge_sort

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前