与big-theta递归相关的big-o和big-omega [英] big-o and big-omega related to big-theta recursion

问题描述

让我们假设一个递归公式是big-o(n ^ 2)，同时又是big-omega(n ^ 2).这是否意味着递归是一个大Theta(n ^ 2)?

Let's suppose that a recursive formula is a big-o(n^2), and at the same time a big-omega(n^2). Does this imply that the recursion is a big-Theta(n^2)?

推荐答案

长话短说:答案是是，确实如此.请参见下面的证明.

To make the long story short: the answer is Yes, it does. See proof below.

尽管每个人都听说过big-o表示法，但可以借助

Though everybody have heard about big-o notation lets recall what exactly does these notations mean with a help of Introduction to Algorithms. For a general case it is said Ο(g(n)), Ω(g(n)), Θ(g(n)), but we will consider yours.

Ο(n ² )表示法定义了一组函数，每个函数都具有以下语句:存在这样的正常数 0≤f(n)≤cn ² 的 c 和 n ₀ 对于所有 n≥n ₀ .

Ο(n²) notation defines a set of functions for each of which the following statement holds: There exists such positive constants c and n₀ that 0 ≤ f(n) ≤ cn² holds for all n ≥ n₀.

所以 f(n)只是Ο(n ² )中的一个函数.示例 13n ， -5 ， 4n ² + 5 .所有这些都与Ο(n ² )有关.

So f(n) is just a function from Ο(n²). Examples 13n, -5, 4n² + 5. All these pertain to Ο(n²).

Ω(n ² )表示法定义了一组函数，每个函数都具有以下语句:存在这样的正常数 0≤cn ² ≤f(n)的 c 和 n ₀ 对于所有 n≥n ₀ .

Ω(n²) notation defines a set of functions for each of which the following statement holds: There exists such positive constants c and n₀ that 0 ≤ cn² ≤ f(n) holds for all n ≥ n₀.

所以 f(n)只是Ω(n ² )中的一个函数.示例 n ⁴ + n-1 ， 3 ⁿ ， n ² -12 .所有这些都与Ω(n ² )有关.

So f(n) is just a function from Ω(n²). Examples n⁴ + n - 1, 3ⁿ, n² - 12. All these pertain to Ω(n²).

Θ(n ² )表示法定义了一组函数，每个函数都具有以下语句:存在这样的正常数 c ₁ ， c ₂ 和 n ₀ 表示 0≤c ₁ n ² ≤f(n)≤c ₂ n ² 适用于所有 n≥n ₀ .

Θ(n²) notation defines a set of functions for each of which the following statement holds: There exists such positive constants c₁, c₂ and n₀ that 0 ≤ c₁n² ≤ f(n) ≤ c₂n² holds for all n ≥ n₀.

再次 f(n)只是Θ(n ² )中的一个函数.这些是其代表 n ² /2 + 3 ， 5n ² .

Again f(n) is just a function from Θ(n²). These are its representatives n²/2 + 3, 5n².

我敢打赌，递归公式是big-o(n ^ 2)，而同时big-omega(n ^ 2)表示您有一个函数(称之为) f (n)关于 Ω(n ² )和Ο(n ² ).

I bet saying that a recursive formula is a big-o(n^2), and at the same time a big-omega(n^2) you meant there is a function (lets call it) f(n) pertaining to Ω(n²) and Ο(n²).

在Ω(n ² )中，我们存在 c ₁ ，其中 c ₁ n ² ≤f(n)成立.根据Ο(n ² )，我们存在 c ₂ ，其中 f(n)≤ c ₂ n ² 成立.因此，我们存在 c ₁ 和 c ₂ ，即 c ₁ n ² ≤f(n)≤c ₂ n ² ，也就是Θ(n ² )是关于.

From Ω(n²) we have existence of c₁ that c₁n² ≤ f(n) holds. From Ο(n²) we have existence of c₂ that f(n) ≤ c₂n² holds. Consequently we have existence of c₁ and c₂ that c₁n² ≤ f(n) ≤ c₂n², that is exactly what Θ(n²) is about.

这篇关于与big-theta递归相关的big-o和big-omega的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！