这已经是将近一年之后了,但我想我有一个答案:偏序发现。
考虑一下对总排序进行排序。您有一个由 n 个对象组成的序列(我们假设它们是不同的),以及一个比较操作,它测试两个元素以查看一个是否小于或等于另一个。
您正在尝试发现元素所在的排列。有 n! 可能的排列,所以你试图发现一个介于 1 和 n 之间的数字!每次比较都会为您提供一点信息。发现一个介于 1 和 n 之间的数!需要发现 log(n!) 位。因此,所需的比较次数也是 log(n!) 位,或者:
log(n!) = n log n + o(n log n) = Ω(n log n) 位
(当然,所有对数都以 2 为底。)
你不能做得比这更好。如果每个查询都为您提供一位信息,并且您需要发现至少 Ω(n log n) 位,那么您需要 Ω(n log n) 比较。如果您认为自己可以做得更好,请与 Shannon、Chaitin 和 Kolmogorov 一起讨论。
但更好的是,已知算法即使在最坏的情况下也能做到(例如堆排序)。从这个意义上说,堆排序是渐近最优的。
(请注意,如果您有一个返回多于一位信息的查询操作,您可以做得更好。例如,如果您能想出一个返回 Ω(log n) 位的查询操作,那么您应该能够以 Ω 排序(n) 时间。有关详细信息,请参阅基数排序。)
这种分析适用于各种算法。在 n 个事物的序列中找到一个事物需要发现一个介于 1 和 n 之间的数字,这意味着发现 log n + O(1) 位。如果您的查询操作返回一位,则需要 Ω(log n) 个查询来进行搜索。(有关详细信息,请参阅二进制搜索。)
我想你可以看到我要去哪里。
现在假设您有 n 个元素,它们具有偏序关系,但您不知道它是什么并且想要找出。但是,您所拥有的是一个比较两个元素 x 和 y 的查询,如果 x 在偏序中小于或等于 y,则返回“true”。
有一个明显的算法可以发现需要 Ω(n^2) 时间的偏序:只需将每个元素与其他元素进行比较。
但这是最优的吗?好吧,查询操作返回一位信息。n 个元素的偏序数由Sloane 的 A001035 给出。如果我没看错的话,这个序列是 Ω(2^(n^2)),这意味着要发现一个偏序,你需要:
Ω(log 2^(n^2)) = Ω(n^2) 位
也就是说,你不能比 Ω(n^2) 时间做得更好,所以这是一个渐近最优算法。
“所以”,我听到你问,“我相信输入的大小是 n。但输出的大小不是O(n^2),所以它实际上是某种深层技术意义上的线性算法?”
也许。我现在真的没有时间详细介绍,但我会用一个问题来回答它。
在普通旧排序的情况下,我们可能会得到 n 个不同的元素。要区分它们,需要用 n 个不同的标签来标记它们。存储 n 个不同的标签意味着存储 n 个数字,每个数字都在 1 和 n 之间。这些数字中的每一个都需要 log n 位来表示它,因此问题的总大小是 n log n bits。那么为什么我们不说堆排序在问题的大小上是线性的呢?