θ(n) 和 O(n) 有什么区别？

有时我会看到 θ(n) 带有奇怪的 θ 符号，中间有一些东西，有时只是 O(n)。这只是因为没有人知道如何输入这个符号而懒得打字，还是它有不同的含义？

简短说明：

如果算法的大小为 θ(g(n))，则意味着随着 n（输入大小）变大，算法的运行时间与 g(n) 成正比。

如果一个算法的复杂度为 O(g(n))，则意味着当 n 变大时该算法的运行时间为at most与 g(n) 成正比。

通常，即使人们谈论 O(g(n))，他们实际上指的是 θ(g(n))，但从技术上讲，这是有区别的。

更技术性地说：

O(n) 表示上限。 θ(n) 表示紧界。 Ω(n) 表示下限。

f(x) = θ(g(x)) 如果 f(x) = O(g(x)) 且 f(x) = Ω(g(x))

Basically when we say an algorithm is of O(n), it's also O(n²), O(n^1000000), O(2ⁿ), ... but a Θ(n) algorithm is not Θ(n²).

In fact, since f(n) = Θ(g(n)) means for sufficiently large values of n, f(n) can be bound within c₁g(n) and c₂g(n) for some values of c₁ and c₂, i.e. the growth rate of f is asymptotically equal to g: g can be a lower bound and and an upper bound of f. This directly implies f can be a lower bound and an upper bound of g as well. Consequently,

f(x) = θ(g(x)) 如果 g(x) = θ(f(x))

类似地，要显示 f(n) = θ(g(n))，只需显示 g 是 f 的上限（即 f(n) = O(g(n))）并且 f 是 f 的下界g（即 f(n) = Ω(g(n)) 与 g(n) = O(f(n)) 完全相同）。简而言之，

f(x) = θ(g(x)) 如果 f(x) = O(g(x)) 且 g(x) = O(f(x))

还有little-oh和little-omega（ω) 表示函数的松散上限和松散下界的符号。

总结一下：

f(x) = O(g(x))（大哦）意味着 的增长率f(x)是 渐近地小于或等于 到的增长率g(x).

f(x) = Ω(g(x))（大欧米伽）意味着 的增长率f(x)是 渐近地大于或 等于的增长率g(x)

f(x) = o(g(x))（小哦）意味着 的增长率f(x)是 渐近地少于这 的增长率g(x).

f(x) = ω(g(x))（小欧米伽）意味着 的增长率f(x)是 渐近地比...更棒这 的增长率g(x)

f(x) = Θ(g(x))(theta) 意味着 的增长率f(x)是 渐近地equal to这 的增长率g(x)

如需更详细的讨论，您可以阅读维基百科上的定义或者查阅经典教科书，例如 Cormen 等人的《算法导论》。