代码之家 › 专栏 › 技术社区 › 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年。

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