大O计算

Question

我当时在学大字号。我知道“大O”指的是：

f(n) E(g(N))或f(n) = O(g(n))

这意味着函数f (n)的增长率不大于g(n)。

现在假设我有一个等式：

5n +2 E(N)

根据上述方程，不应该'n‘等于g(n)，'5n+2’等于f(n)。对于n，f(n)的任何值，总是大于g(n)。那么，在这种情况下，大O有多大呢？

Answer 1

你应该更详细地阅读“大欧”的概念。

关系

f(n) E O(g(n)) 

他说

对于某些常数C

f(n) <= C * g(n)

在这种情况下，C是5n +2总是小于Cn的值。

如果你解决了它：

5n + 2 <= Cn

2 <= (C - 5)*n

由此你可以很容易地发现，如果C=6，那么对于n的任何值，你的方程总是成立的！

希望这能有所帮助！

Answer 2

这不是大O符号的正确定义。If f(x) is O(g(x))，则必须存在一些常数C和N，使得：|f(x)| <= C |g(x)| for all x>N。因此，如果f(x)总是小于或等于某个x值后面的常数* g(x)，那么f(x) is O(g(n))。实际上，这意味着常数因素是不相关的，因为您可以选择C作为任何值。所以，举个例子，f(n)=5n+2 <= C*g(n)=10000n So，f(n) is O(g(n))。

Answer 3

考虑到大O表示法代表的是什么，你就有了这个说法。

5n +2 E O(n)

或5n +2 = O(n)

鉴于Big表示法对我们的函数有一个上限，即为我们给定的函数的可能结果建立一个上限，则可以以下列方式重新考虑这个问题：

5n +2 <= c*n，对于某些常数c*n

我们可以看到，这个说法是正确的，因为它是有可能找到一些常数，将大于或等于我们的函数(使常数大小，我们需要)。

广义上，如果g(n)的度大于或等于f(n) E 211的度，则任意给定函数f(N)将属于O(g(n)) >，即其项中的最高度。

形式:设f(n) = n^x；g(n) = n^y；使x <= y

然后f(n) = O(g(n))。

同样的情况也适用于大欧米茄，另一种情况则是如此。希望它对你有用