证明 Big Oh 时如何 select n0 的值 - 哪个是正确的方法？

Question

考虑问题，

证明 f(n) = n² + 3 是 O(n²).

我知道我们需要找到两个正常数 c 和 n₀ 使得 n>=n₀ 和 f(n )<=c*g(n)。

所以会是：

n²+3 <= c*g(n²) .................. {代入 g(n) = n²}

n²+3 <= c*n².......{假设 n ₀ >=1 并替换值}

1+3 <= c*1.......{n²=1*1=1}

4<=c

因此当 C=4 且 n₀>=1 时，我得到解 f(n) 是 O(n²)

但是，请考虑以下事项。

n²+3 <= c*n².......{假设 n ₀ >=2 并替换值}

2²+3 <= c*2²

4+3 <= c*4

7 <= 4*c

如果 c = 2

7<=4*2....满足所有n₀ >=2

这也证明f(n)是O(n²).

哪种方法是正确的，为什么？

我如何select c 和 n₀ 的最优值？

注意：我从 Proving and Disproving BigO 得到这个例子，它使用了另一种我不理解的证明方法。

Answer 1

我认为你的问题有问题。 我认为你的问题是证明 f(n) = n² + 3 是 O(n²) 并且 g(n) 必须给出n² 在问题本身。 （你不能假设 g(n) 为 n²）。

如何选择c和n₀ :

参考这个例子：http://web.eecs.utk.edu/~booth/311-01/notes/bigOex.html

基本上，你可以选择符合你直觉的c和n₀。如您所料，c 和 n₀ 可以有多种可能性。