algorithm - 通过减少确定的下限是否严格？

将问题 A 简化为问题 B 意味着问题 B 至少和 A 一样难，甚至更难。

如果我可以将排序减少到其他一些问题 X，我知道 X 的下限为 Omega(n log n)。
该下限是否保证是紧下限？我怀疑它不应该是，因为只知道 X 至少和 A 一样硬——这意味着它可能更难，因此有不同的下限。

我的意思是说，因为插入排序具有 O(n^2) 的最坏情况紧上界是正确的，所以说它具有 O(n^2) 的最坏情况运行时间也是正确的3)。这是正确的，但没有太大的实用值(value)——因为我们 99% 的时间都对紧边界感兴趣。

最佳答案

你说得对，界限不需要太紧。

例如，考虑一个简单的例子:在 n 整数数组中找到最小的整数。每次都有O(1)空间和O(n)时间算法来解决这个问题。然而，这个问题归结为通过减少 O(1) 两种方式对整数数组进行排序的问题:

将 MININT 输入转换为 SORTINT 输入:将 MININT 的输入直接用于 SORTINT 。

将 SORTINT 输出转换为 MININT 输出:返回排序数组的第一个元素(假设元素按升序排序)。

对于最坏情况的输入，排序确实有 Omega(n) 的下限。这不是一个严格的界限； Omega(n lg n) 对于 SORTINT 更严格。但是将 MININT 减少到 SORTINT 本身并没有告诉我们这一点。

关于algorithm - 通过减少确定的下限是否严格？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45170888/