我正在修改 Big O 和其他相关界限的正式定义，但有些事情让我绊倒了。在我正在读的书中（Skiena），Big O 被定义为：
f(n) = O(g(n)) 当存在常数 c 时，对于 n > n0 的某个值，f(n) 始终
这对我来说通常是有意义的。我们只关心足够大的 n 值，以至于增长率实际上很重要。但为什么要把 g(n) 乘以 c 呢？看起来我可以为 c 选择一个非常大的值，并通过消除较小的 g(n) 值的大小来使整个事情变得任意。
第二个问题：当选择将算法分类为复杂性类别时，一般的经验法则是只选择根据 Big O 的定义仍然成立的最低增长类别吗？根据定义，将恒定时间算法分类为 O(n!) 似乎是有效的，因为 f(n) 将
Thanks!
你可以乘以g(n)由任意常数c是因为你想要的函数只是一个常量c因素远离f(n)。简单来说，您根据以下内容进行分析n，而不是常量，所以您关心的是这些函数如何仅根据输入大小而变化。例如当你有n^3 and n你无法选择c where c*n >= n^3 unless c >= n^2这不再是恒定的，所以g(n)将会逃离f(n) with n.
正如埃德提到的，这个分析不会给你一个确切的运行时间，但会给出一个增长率取决于输入n. If g(n) and f(n)彼此之间始终仅（至多）相差一个常数因子，而两者的增长率将相同。
在这种时间复杂度分析中，我们并不真正关心常量，这在大多数情况下是可以的but在某些情况下，您实际上应该考虑到这一点。例如，如果您正在处理小型集合，则由于常量，O(n^2) 算法实际上可能比 O(nlogn) 更快。
第二个问题：是的，这是一个常见问题BigO，您可以使用任意函数，这就是为什么我们通常试图找到“最紧”的函数g(n)我们可以，否则找到它就没有意义了。这也是为什么*大西塔比BigO因为它告诉你一个紧界，而不是上限。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
