complexity-theory - 如果算法时间复杂度为 theta(n^2)，是否有可能对于一个输入它会在 O(n) 中运行？

Question

如果算法时间复杂度为 theta(n^2)，是否有可能对于一个输入它会在 O(n) 中运行？根据 theta 的定义，似乎没有输入将在 O(n) 中运行。但是有人说这是可能的。

我真的想不出在 theta(n^2) 中运行的算法会有一个可能在 O(n) 中运行的输入。

如果是真的，你能给我解释一下并举个例子吗？

非常感谢！

Answer 1

我认为您的术语正在绊倒您。

算法不能是“Θ(n ² )”。Theta 表示法描述了函数的增长率。你可以说一个算法的运行时间是 Θ(n ² )，在这种情况下，算法在任何输入上都不能在 O(n) 时间内运行，或者你可以说一个算法的最坏情况运行时间是 Θ(n ² )，在在这种情况下，可以想象算法将在 O(n) 时间内运行某些输入（例如，插入排序）。

希望这可以帮助！

Answer 2

如果算法时间复杂度为 theta(n^2)，是否有可能对于一个输入它会在 O(n) 中运行？

不，这就是为什么。假设您的算法的运行时间是f(n). 从那时f(n) = Θ(n)起，我们将拥有一些常量，c0>0并且对于每个. 让我们假设。这意味着对于某些常量，我们将拥有每个. 那么对于我们来说， 这对于 来说是不正确的。矛盾。n0>0c0*n^2 <= f(n)n >= n0f(n) = O(n)c1>0, n1>0f(n) <= c1*nn>=n1n >= max(n1, n2)c0*n^2 <= f(n) <= c1*n => c0*n <= c1n > c1/c0

非正式地，你总是可以认为Oas<=和Θas =（和Ωas >=）。因此，您可以将问题重新表述为：

如果某个值等于 n^2 是否小于 n？

Answer 3

我的理解是，虽然 Big-Oh 只断言上限，但 Big-Theta 断言上限和下限。根据定义，如果某项在 中执行theta(n^2)，则没有执行为 的输入theta(n)。

注意：这些都指的是渐近复杂度。算法可以在较小的输入上以不同的方式执行，即，由于隐藏的常数因素，运行的算法theta(n^2)可能优于（在较小的输入上）运行的算法。theta(n)