不使用O(f(n))或Ω(f(n)),Θ(f(n))的正式定义是什么?
不借助O或Ω的Θ(f(n))直接定义
通常我们会通过O(f(n))和Ω(f(n))来定义Θ(f(n)),但完全可以直接给出它的原生定义:
对于函数g(n)和f(n),当且仅当存在正常数c₁、c₂和n₀,使得对于所有满足n ≥ n₀的整数n,都成立:c₁·f(n) ≤ |g(n)| ≤ c₂·f(n)
此时我们称g(n) = Θ(f(n))。
这个定义本质上是把O(渐进上界)和Ω(渐进下界)的约束合并到了同一条表述中,逻辑上和O、Ω的定义同源,但无需借助这两个符号就能独立表述。
内容的提问来源于stack exchange,提问作者BigMistake
相关产品推荐
相关产品推荐

