algorithm - 理解大 O 符号

Question

一些关于算法的标准书籍产生了这一点：

0 ≤ f( n ) ≤ c⋅g( n ) 对于所有n > n ₀

在定义 big-O 时，谁能向我解释这意味着什么，使用一个可以帮助我更准确地可视化和理解 big-O 的强大示例？

Answer 1

假设您有一个函数f(n)并且您正在尝试对它进行分类 - 它是不是某个其他函数的大g(n)O。

定义基本上说f(n)如果O(g(n))存在两个常数 C,N 使得

f(n) <= c * g(n) for each n > N

现在，让我们了解它的含义。

从部分开始n>N- 这意味着，我们不“关心” 的低值n，我们只关心高值，如果某些（最终数量）低值不符合标准 - 我们可以通过选择N更大来默默地忽略它们然后他们。

看看下面的例子：

虽然我们可以看到，对于 n: 的低值n^2 < 10nlog(n)，第二个很快赶上，并且在N=10我们得到所有n>10声明之后10nlog(n) < n^2是正确的，因此10nlog(n)在O(n^2). 常数c意味着我们也可以通过常数因子容忍一些倍数，并且我们仍然可以接受它作为期望的行为（例如，用于证明5*nis O(n)，因为没有它我们永远无法为每个: 找到N这样的，但是有了常数，我们可以使用 c=6 并显示并获取.n > N5n < nc5n < 6n5nO(n)

Answer 2

这个问题是一道数学题，不是算法题。

你可以在这里找到一个定义和一个很好的例子：https ://math.stackexchange.com/questions/259063/big-o-interpretation

正如@Thomas 指出的那样，维基百科也有一篇很好的文章：http ://en.wikipedia.org/wiki/Big_O_notation

如果您需要更多详细信息，请尝试提出更具体的问题。