algorithm - Big O 正式定义中的常量

Question

我正在修改 Big O 和其他相关边界的正式定义，但有些事情让我感到困惑。在我正在阅读的书 (Skiena) 中，Big O 被定义为:

f(n) = O(g(n)) 当存在常数 c 时 f(n) 总是 <= c*g(n) 对于 n > n0 的某个值

这对我来说通常是有意义的。我们只关心足够大的 n 值，以至于增长率实际上很重要。但为什么要将 g(n) 乘以 c？似乎我可以为 c 选择一个非常大的值，并通过扩大较小的 g(n) 值的大小来使整个事情变得任意。

次要问题:在选择将算法归入复杂度类别时，根据大 O 的定义，一般的经验法则是只选择仍然成立的最低增长类别吗？根据定义，将常数时间算法归类为 O(n!) 似乎是有效的，因为 f(n) 将 <= c*g(n)。当然，这没有任何值(value)。

谢谢!

Answer 1

您可以将 g(n) 乘以任意常数 c 是因为您想要的函数只有一个常数 c 因子远离f(n)。简单来说，您根据 n 而不是常量执行分析，因此您关心的是这些函数如何仅根据输入大小而变化。例如，当您有 n^3 和 n 时，您无法选择 c，其中 c*n >= n^ 3 除非 c >= n^2 不再是常数，所以 g(n) 将远离 f(n) 与 n。

正如 Ed 所提到的，此分析不会为您提供准确的运行时间，而是根据输入 n 提供增长率。如果 g(n) 和 f(n) 总是(至多)彼此相差一个常数因子，那么两者的增长率将相同。

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

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