由约化确定的下限是否严密?

你是绝对正确的,界限不需要很紧。

例如,考虑一个简单的示例:在 n 整数。有一个 O(1) O(n) 时间算法每次都要解决这个问题。然而,这个问题归结为通过减少 O(1)

1. 正在转换 MININT 输入到 SORTINT MININT公司 的输入直接用于 索丁 .
2. MININT公司 输出:返回已排序数组的第一个元素(假设元素按升序排序)。

在最坏情况下的输入上,排序当然有欧米茄(n)的下限。这不是一个严格的约束;欧米茄(n lg n)对于 .但是 到 索丁