big-o 和 big-omega 与 big-theta 递归相关

Question

假设一个递归公式是一个big-o(n^2)，同时也是一个big-omega(n^2)。这是否意味着递归是 big-Theta(n^2)？

Answer 1

长话短说：答案是是的。请参阅下面的证明。

尽管每个人都听说过 big-o 符号，但让我们借助 Introduction to Algorithms 回忆一下这些符号的确切含义。对于一般情况，据说 O(g(n))、Ω(g(n))、Θ( g(n))，但我们会考虑你的。

O(n²)

O(n²) 表示法定义了一个 函数集 每个函数以下陈述成立：存在这样的正常数 c 和 n₀ 使得 0 ≤ f(n) ≤ cn² 对所有 n ≥ n₀[=143= 成立].

所以 f(n) 只是 O(n²) 的一个函数.例子 13n, -5, 4n² + 5 .所有这些都属于 O(n²).

Ω(n²)

Ω(n²) 表示法定义了一个 函数集 每个函数以下陈述成立：存在这样的正常数 c 和 n₀ 使得 0 ≤ cn² ≤ f(n) 对所有 n ≥ n₀[=143= 成立].

所以 f(n) 只是 Ω(n²) 的一个函数.示例 n⁴ + n - 1, 3ⁿ , n² - 12。所有这些都属于 Ω(n²).

Θ(n²)

Θ(n²) 符号定义了一个 函数集 每个以下陈述成立：存在这样的正常数 c₁, c₂ 和 n₀ 即 0 ≤ c₁n² ≤ f(n) ≤ c₂n² 对所有 n≥n₀。

同样 f(n) 只是 Θ(n²) 的一个函数.这些是它的代表 n²/2 + 3, 5n².

证明

我打赌说递归公式是一个 big-o(n^2)，同时也是一个 big-omega(n^2) 你的意思是有一个函数（让我们称之为）f(n) 属于 Ω(n²) 和 Ω(n²).

从Ω(n²)我们有c_{1[=152的存在=]} 即 c₁n² ≤ f(n) 成立。从 O(n²) 我们有 c₂[=143 的存在=] f(n) ≤ c₂n² 成立。因此，我们存在 c₁ 和 c₂ c₁n² ≤ f(n) ≤ c₂n²，这正是 Θ(n²) 的意思。