如果不以 O(f(n)) 或 Ω(f(n)) 表示 θ(f(n))，那么 θ(f(n)) 的正式定义是什么？

Question

θ 或 θ(f(n)) 通常用 O(f(n)) 或 Ω(f(n)) 来定义。本网站上的其他答案以这种方式定义 θ(f(n)) 。不使用 O 或 Ω 时 θ(f(n)) 的定义是什么？

当然，因为 g(n) = θ(f(n)) 当且仅当 g(n) = O(f(n)) 且 g(n) = Ω(f(n)) 时，定义不使用 O 或 Ω 的 θ(f(n)) 仍会以某种方式反映 O 和 Ω 的定义。

Answer 1

如果存在正数

h(n)

和

Θ(k(n))

，且超过某个值

p

、

q

≤

n

且

h(n)

≥

p * k(n)

，则函数

h(n)

位于

q * k(n)

中。