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 符号描述函数的增长率。你可以说算法的 runtime 是 Θ(n²)，在这种情况下，算法不能在任何输入上及时运行 O(n)，或者你可以说一个算法的最坏情况运行时间是 Θ(n²)，在这种情况下，可以想象该算法对于某些输入的运行时间为 O(n) (以插入排序为例)。

希望这对您有所帮助!