algorithm - 寻找 Big Oh 的值(value)

Question

我正在查看 here 中的渐近符号。我正在读这个f(n) ≤ c g(n)

例如，如果f(n) = 2n + 2，我们可以通过调整的值以任何方式满足它，因为f(n)是O(c.g(n)) >n 和 c。或者c和n的取值有没有具体的规则或公式。 no 永远是 1 吗？

Answer 1

本身没有公式。您可以在这里找到正式定义:

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n. (big-O notation)。

我从你的问题中了解到的是，你没有得到大O表示法的本质。例如，如果您的复杂度是 O(n^2) ，那么你可以保证在f(n)之后有某个n值(大于k)在任何情况下都不会超过c g(n) .

让我们尝试证明f(n) = 2n + 2是 O(n) :

1. 从函数本身看来，您无法设置 c 的值等于 2如您所愿 f(n) ≤ c g(n) 。如果您插入 c = 2 ，你必须找到k这样f(n) ≤ c g(n)对于 n ≥ k 。显然，没有 n其中2n ≥ 2n + 2 。所以，我们继续c = 3 .

2. 现在，让我们找出 k 的值。所以，我们求解方程3n ≥ 2n + 2 。解决办法:

   3n ≥ 2n + 2 => 3n - 2n ≥ 2 => n ≥ 2

因此，对于 c = 3 ，我们发现值 k = 2 (n≥k)。

你也必须明白，你的功能不仅仅是O(n) 。也是O(n^2), O(n^3), O(n^4)等等。都是因为 c 的对应值和k存在于g(n) = n^2 , g(n) = n^3和g(n) = n^4 .

希望有帮助。