algorithm - Big-O 和 Big-theta 可以互换使用吗？

Question

我正在研究 Thomas H. Corman 的《算法导论》一书。我正在研究渐近符号。一件事困扰着我，因为作者说：

f(n)=Big-theta(g(n)) 意味着 f(n)=Big-O(g(n)) ，因为 Big-theta 表示法比 O-表示法更强。 如何？？

并且作者还表示(an^2+bn+c)，其中 a>0，在Big-theta(n^2)中也表明这种二次函数在Big-O(n^2)中。如何？？

Answer 1

我认为您对这些条款有些困惑。

f(n) = O(g(n))- 表示这g(n)是 的上限f(n)。正式存在 const n0, c，这样对所有的n>n0, f(n)<= c*g(n)。你可以把它想象成两个图，c*g(n)比f(n). 例如 ：5n^2+n = O(n^2)

为什么 ？

因为如果，例如，n0=10and c=10，那么对于所有n>n0-5n^2+n <= 10*n^2

f(n) = Theta(g(n))- 表示g(n)是 的上限和下限f(n)。正式存在 const n0, c1, c2，这样对所有的n>n0, c1*g(n)<=f(n)<=c2*g(n)。您可以将其想象为三个图形，例如f(n)介于c1*g(n)和之间c2*g(n)。例如 ：5n^2+n = Theta(n^2)

为什么 ？

因为如果，例如，n0=100然后c1=1,c2=100对于所有n>n0-n^2<=5n^2+n<=100*n^2

Answer 2

（在本书的 V1 中）f() 在 Theta(g(n)) 中的定义是存在正常数 C1 和 C2 使得 0 <= C1g(n) <= f(n) <= C2g( n) 对于所有 n >= N0

O(g(n)) 的定义是存在一个 C 使得 0 <= f(n) <= Cg(n) for all n >= N0

所以如果你能找到足够大的常数 N0、C1 和 C2 来满足第一个定义，你可以使用常数 N0 和 C = C2 来满足第二个定义。因此，第一个定义比第二个定义更强，因为任何满足第一个定义的东西都满足第二个定义——关于二次的业务是这种情况的一个特例。