我们什么时候会考虑渐近符号中的常数？

Question

我认为：忽略常量应该有一个限制！

当常数变得太大时，我们应该考虑它，因为它会产生巨大的差异

有什么规定吗？

Answer 1

请注意，当我们谈论渐近行为时，我们描述的是限制行为。

如果你深入了解任何渐近分析符号（Big Oh、Big Theta、Big Omega）的细节，你会发现常数，对于本质上所有感兴趣的情况，实际上对结果没有影响我们对函数或算法渐近行为的分析。

举个例子，让我们粗略地看一下Big-O符号的定义：

f(n) is said to be in O(g(n)) if we can find any positive set of constants k and N, such that |f(n)| ≤ k · |g(n)| holds for all n > N.

现在，假设 f(n) 是线性的

f(n) = n + C

并且 C 是一个可怕的巨大常数。即使在这种情况下，常数对于 f(n) 的渐近或限制行为也不感兴趣。根据上面的定义，我们可以选择自己的常量 k 足够大，使得下面的

k·n > C, for all n > N

即我们在对f(n)进行渐近分析的过程中，可以随意选择k，甚至等于C。这将产生（假设 N>1，因此 n>1）

f(n) = n + C < { n > 1 } < n + n·C = { choose k = C } 
             = n + n·k < 2kn = { set l = 2k } = l·n
             = { g(n) = n } = l·g(n)

由此，我们证明了 f(n) is in O(n)，即使 f(n) 中的常数项 C 是 "hideously huge" .

这同样适用于您可以编写的任何类型的函数或算法；常数项对函数的 渐近行为 没有影响，无论它们有多大（我们研究限制行为，而不是状态！）。即使对于常数函数，比如 h(n) = C，C 的大小是否会对我们的渐近分析结果产生任何影响（此处为 Big-O）；我们可以自由地选择 k 并很容易推导出 h(n) is in O(1)（即 恒定时间 ：计算时间不会随着问题规模的增长而增加，例如哈希 table 查找）。

现在，您当然可以在一般上下文中查看大常数项在函数和算法中的重要性，但是根据上述内容，这与渐近分析。

有关多项式渐近分析 (Big-Oh) 中常数的增加如何对分析结果没有任何影响的示例，请参见：

我们什么时候会考虑渐近符号中的常数？

When we will consider the constants in asymptotic notations?

constants

asymptotic-complexity

notation