谁首先证明了所有基于比较的排序至少是 Omega(n lg n)？ 这个下界有名字吗？例如SomeGuysLastName 定理？
最佳答案
我的“Introduction to Algorithms”副本在第 8 章的章节注释中是这样说的，这是讨论这个边界的地方:
The decision-tree model for studying comparision sorts was introduced by Ford and Johnson (1). Knuth's comprehensive treatise on sorting (2) covers many variations of the sorting problem, including the information-theoretic lower bound on the complexity of sorting given here.
(1) Lester R. Ford, Jr. and Selmer M. Johnson. A tournament problem. The American Mathematical Monthly, 66:387-389, 1959.
(2) Donald E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, 1973.
不是您问题的明确答案，但它是某种东西。
关于algorithm - 谁首先证明了所有基于比较的排序都是 Omega(n lg n)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4111031/