渐近复杂度是常数，为什么是常数？
大 oh 表示法表示，对于某个常数 c，所有 g(n) 都是元素 cf(n)，O(g(n))。
我一直想知道并且从未真正理解为什么我们需要这个任意常数与边界函数 f(n) 相乘以获得边界？
另外，如何决定这个常数应该是多少？
Big oh notation says that all g(n) are an element c.f(n), O(g(n)) for some constant c.
I have always wondered and never really understood why we need this arbitrary constant to multiply with the bounding function f(n) to get our bounds?
Also how does one decide what number this constant should be?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
该常数本身并不表征 f(n) 与 g(n) 相比的限制行为。
它用于数学定义，强制常量 M 的存在，使得
如果存在这样的常量，则你可以说f(x)是一个O(g(x))，这是分析算法时的常用表示法，你不关心哪个是常数，而只关心运算本身的复杂性。该常数能够通过确保 M|g(x)| 是 f(x) 的上限来纠正不方程。
如何找到该常数取决于 f(x) 和 g(x)，并且必须证明这一数学点才能确保 f(x) 具有 ag(x) big-o，因此没有通用规则。查看这个示例。
The constant itself doesn't characterize the limiting behavior of the f(n) compared to g(n).
It is used for the mathematical definition, which enforces the existence of a constant M such that
If such a constant exists then you can state that f(x) is an O(g(x)), and this is the usual notation when analyzing algorithms, you just don't care about which is the constant but just the complexity of operations itself. The constant is able make that disequation correct by ensuring that M|g(x)| is an upper bound of f(x).
How to find that constant depends on f(x) and g(x) and it is the mathematical point that must be proved to ensure that f(x) has a g(x) big-o so there's not a general rule. Look at this example.
考虑函数
调用此函数
O(n)是否有意义，因为它的增长速度与g(n) = n一样快。但是如果
O的定义中没有常量，您就无法找到n0，例如对于所有n > 的情况。 n0，f(n) <= n。这就是为什么你需要常量，实际上从条件来看，你可以得到
n0 == 0, c == 4。Consider function
Doesn't it make sense to call this function
O(n)since it grows "as fast" asg(n) = n.But without constant in definition of
Oyou can't findn0such as that for alln > n0, f(n) <= n. That's why you need constant, and indeed from condition,you can get
n0 == 0, c == 4.