Big O正式定义中的常量 [英] Constants in the formal definition of Big O

问题描述

我正在修改Big O以及其他相关范围的正式定义，这让我感到震惊。在我正在读的书（斯基纳）中，大O定义为：

I'm revising the formal definitions of Big O and the other associated bounds and something is tripping me up. In the book I'm reading (Skiena) Big O is defined as:

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

f(n) = O(g(n)) when there exists a constant c such that f(n) is always <= c*g(n) for a some value of n > n0

我们只关心足够大的n值，而增长率实际上很重要。但是，为什么将g（n）乘以c？似乎我可以为c选择一个非常大的值，并通过吹出较小的g（n）值来使整个事情变得任意。

This generally makes sense to me. We are only concerned with large enough values of n that the growth rates actually matter. But why multiply g(n) by c? It seem like I could choose a very large value for c, and make the whole thing arbitrary by blowing out the size of smaller g(n) values.

次要问题：当选择将算法归类为复杂性类别时，通常的经验法则是仅根据的定义选择仍保留的最低增长类别大O？根据该定义，将恒定时间算法归类为O（n！）似乎是有效的，仅因为f（n）将小于等于c * g（n）。当然，这没有任何价值。

Secondary question: When choosing to classify an algorithm into a complexity class, is the general rule of thumb to just choose the lowest growth class that still holds according to the definition of Big O? According to the definition it seems valid to classify a constant time algorithm as O(n!), simply because f(n) will be <= c*g(n). Off course this offers no value.

谢谢！

推荐答案

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

You can multiply g(n) by an arbitrary constant c is because you want functions that are only a constant c factor away from f(n). In simple terms you perform your analysis based on n, not constants so what you are concerned with is how those functions change depending on the input size only. For instance when you have n^3 and n there's no way you can choose a c where c*n >= n^3 unless c >= n^2 which isn't constant anymore so g(n) will be running away from f(n) with n.

正如Ed所提到的那样，该分析不会为您提供确切的运行时间，而是增长率，具体取决于输入 n 。如果 g（n）和 f（n）始终只是（最多）彼此远离的常数两者的增长率将相同。

As Ed mentioned this analysis won't give you an exact run time but a growth rate depending on input n. If g(n) and f(n) are always only (at most) a constant factor away from each other than the growth rate will be the same for both.

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

In this kind of time complexity analysis we don't really care about constant which in most cases is ok but in some cases you actually should take it into account. For instance if you are working on small sets an O(n^2) algorithm might actually be faster than O(nlogn) because of constants.

第二个问题：是的，这是 BigO 的常见问题，您可以使用任意函数，这就是我们通常尝试查找最严格的 g（n），否则找到它就没有多大意义了。这就是为什么 * BigTheta 比 BigO 有用得多的原因，因为它告诉您一个严格的界限，而不是上限。

Second question: yes this is a common problem with BigO, you can use an arbitrary function that's why we usually are trying to find the "tightest" g(n) we can, otherwise there's no much point in finding it. That's also why *BigTheta is much more useful than BigO as it tells you a tight bound, instead of an upper bound.

这篇关于Big O正式定义中的常量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！