Big O正式定义中的常量

Big O正式定义中的常量

您可以乘以

g(n)

任意常数

c

是因为您想要的功能

c

离仅有一个常数因子

f(n)

。简而言之，您将基于而

n

不是常量执行分析，因此您所关心的是这些函数如何根据输入大小而变化。例如，当您拥有

n^3

并且

n

没有办法时，您无法选择一个

c

位置，`c*n

= n^3

除非

c >= n^2

该位置不再恒定，因此

g(n)

将

f(n)

与with 分开

n`。

正如Ed所提到的，该分析不会给您确切的运行时间，而是取决于输入 n* 的 增长率
。如果和始终（至多）始终是一个恒定的相互远离的因素，那么增长率将是相同的。
*

g(n)``f(n)

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

第二个问题：是的，这是 BigO* 的常见问题，您可以使用任意函数，这就是为什么我们通常试图找到

g(n)

我们能找到的“最紧密的”
函数，否则找到它就没有多大意义了。这就是 BigTheta 比 BigO 有用的 原因，**
因为它告诉您一个紧密的界限，而不是一个上限。