它要求指出函数所属的类 Big-Theta(g(n)) 并证明断言。
在这种情况下 f(n) = (n^2+1)^10
根据定义 f(n) E Big-Theta(g(n)) <=> c1*g(n) < f(n) < c2*g(n)，其中 c1 和 c2 是两个常数。
我知道对于这个特定的 f(n)，Big-Theta 是 g(n^20)，但我不知道谁来正确证明它。我想我需要操纵这种不平等，但我不知道如何
问问题
12066 次
2 回答
2
函数 f(x) 是 Θ(g(x))，当且仅当：
- f(x) 是 O(g(x))，并且
- g(x) 是 O(f(x))
因此，虽然您可以尝试用一个不等式来证明它，但我建议您将其分解为这两部分；首先证明对于一些 n>n 0 f(n) < c 1 g(n)，然后证明对于一些 N > N 0 g(N) < c 2 f(N)。一旦你分别证明了这两个部分，你就可以回到 Θ 的定义来证明 f = Θ(g)。
于 2010-04-27T04:14:42.963 回答
0
我不是这方面的专家，但你不能证明 f(n) E Ο(n) 和 f(n) E Ω(n) 然后证明 f(n) E Θ(n)由于交集的定义？
于 2010-08-13T21:40:28.387 回答