大O符号的正式定义中的常量

Question

我正在修订Big O和其他相关边界的正式定义，但有些事情让我困扰。在我正在阅读的书（Skiena）中，Big O被定义为：

当存在常数c使得f(n)总是<= c*g(n)时，f(n) = O(g(n))，其中n > n0

这通常对我来说很有意义。我们只关心足够大的n值，以便增长速率真正有影响。但是为什么要将g(n)乘以c呢？似乎我可以选择一个非常大的c值，并通过扩大较小的g(n)值的大小来使整个过程变得任意。

次要问题：在选择将算法分类为复杂度类时，一般的经验法则是只选择最低的增长类，而仍然符合Big O的定义吗？根据定义，将常量时间算法分类为O(n!)似乎是有效的，因为f(n)将<= c*g(n)。当然，这并没有提供任何价值。

谢谢！

- Justin

---

大O符号只是描述了随着问题规模变化，内存/时间如何改变。它不告诉你实际的时间等。你选择最大的那个。例如，n^2比n等。 - Ed Heal

我不确定那是否回答了我的问题。是的，它告诉你随着输入大小时间如何变化，但它应该提供一个上限。因此，您需要选择最紧密的上限，对吧？否则，它根本不能代表增长。我仍然不确定常数c如何发挥作用。 - Justin

不是的 - 它描述了增长 - 即图形的形状。 c 只是其中一个轴的拉伸值。不会改变图形的形状。 - Ed Heal

根据定义和严格的从左到右阅读特殊“=”符号的含义，O(n) = O(n^2) = O(n!)。是的，这并没有提供任何价值。然而，有时候确定某个东西是O(n^2)比实际确定它是O(n^1.987)更容易，这样可以有点懒惰但仍足够准确。 - Ulrich Eckhardt

对于未来的读者，这可能会有所帮助：https://dev59.com/Sl0a5IYBdhLWcg3wxrON - csguy

Answer 1

您可以将g(n)乘以任意常数c，因为您希望函数与f(n)仅相差一个常数c。简单来说，您基于n进行分析，而不是常数，因此您关心的是这些函数如何随着输入大小而变化。例如，当您有n^3和n时，除非c>=n^2，否则没有办法选择c使得c*n>=n^3，这不再是常数，因此g(n)会随着n而逃离f(n)。

正如Ed所提到的，这种分析不会给出确切的运行时间，而是根据输入n给出一个增长率。如果g(n)和f(n)之间始终只相差（最多）一个常数因子，则增长率将对两者都相同。

在这种时间复杂度分析中，我们并不真正关心常数，在大多数情况下这是可以接受的但是在某些情况下，您实际上应该考虑它。例如，如果您正在处理较小的集合，则O(n^2)算法可能比O(nlogn)更快，因为存在常数。

第二个问题：是的，这是BigO的常见问题，您可以使用任意函数，这就是我们通常尝试找到最“紧密”的g(n)的原因，否则找到它没有多大意义。这也是为什么BigTheta比BigO更有用，因为它告诉您一个紧密的上界，而不是一个上界。

- Mateusz Dymczyk

---

Big Theta提供更紧密的上限吗？还是仅提供上限和下限，从而为您提供更具代表性的增长范围？ - Justin

它给出上限和下限，这意味着它是一个紧密的界限（upper == lower）。当BigO == BigOmega时，就会出现大theta，没有范围涉及。 - Mateusz Dymczyk

好的，让我试着通过Ed Heals的评论来澄清一下。c的值并不重要，因为它不会改变图形的形状（当你绘制g(n)的图形时），它基本上只是将线条向上移动。因此，随着y值以相同的速率增加，增长率仍然是相同的。这对我来说很有道理，但我为什么需要c呢？它是用来补偿我们在f(n)中忽略常数的事实吗？因此，如果我们不引入c，f(n)在图表上看起来可能会更大？ - Justin

那么这样做的目的是因为f(n)很可能包含常数，因此g(n)（作为增长率的抽象版本）将无法为f(n)提供上界。这正确吗？ - Justin

当我重新阅读Big theta的定义时，它终于让我恍然大悟。加上一些常数c1和减去一些常数c2，g(n)为f(n)提供上限和下限。当然，只有在增长率与n趋近于无穷大时才可能出现这种情况！因此，Big Theta基本上是在说g(n)不是任意的上限或下限，它就是增长率，这就是人们为什么说它是一个紧密的约束。我感觉自己像在Matrix中，看到的全是绿色滚动的代码 :P - Justin

Answer 2

当选择将算法分类到复杂度类别时，一般的经验法则是根据大O符号的定义选择最低的增长类别。在符号方面，就像我们有用于上界的大O符号一样，我们也有用于下界的大Omega符号和用于显示上界和下界相匹配的大Theta符号。

https://en.wikipedia.org/wiki/Big_O_notation#The_Knuth_definition

假设 Knuth 的引用是正确的，那么我们可以说，在假设涉及紧密渐近界限的结果更有用时，您并不孤单 :) 有时人们说 big-O 时实际上意思是 big-Theta，但有时他们只是不在意或者还没有找到下限。

看起来我可以选择一个非常大的 c 值，并通过扩大较小 g(n) 值的大小使整个过程变得任意。

对于具有不同渐近增长率的函数，c 值并不重要。无论您选择 c 多大或多小，都会有一个 n 值，当较快增长的函数追上时。常数因子存在是为了让您忽略当事物具有相同增长率时的常数乘数。例如，就大 O 而言，f(x) = 2x 和 g(x) = 3x 都具有相同的增长率。

- hugomg

---

你的评论“无论你选择c有多大或多小，总会有一个n使得更快增长的函数追上它”，非常有用。谢谢！ - Justin