与big

本文介绍了与big-theta递归相关的big-o和big-omega的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

让我们假设一个递归公式是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表示法，但可以借助算法简介.在一般情况下，称为Ο(g(n))，Ω(g(n))，Θ(g(n)) ，但我们会考虑您的.

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 2 )表示法定义了一组函数，每个函数都具有以下语句:存在这样的正常数 0≤f(n)≤cn 2 的 c 和 n 0 对于所有 n≥n 0 .

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

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

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

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

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

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

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

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

Θ(n2) notation defines a set of functions for each of which the following statement holds: There exists such positive constants c1, c2 and n0 that 0 ≤ c1n2 ≤ f(n) ≤ c2n2 holds for all n ≥ n0.

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

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

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

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 Ω(n2) and Ο(n2).

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

From Ω(n2) we have existence of c1 that c1n2 ≤ f(n) holds. From Ο(n2) we have existence of c2 that f(n) ≤ c2n2 holds. Consequently we have existence of c1 and c2 that c1n2 ≤ f(n) ≤ c2n2, that is exactly what Θ(n2) is about.