The*_*ged 0 algorithm complexity-theory
让 f(n)= ( (n^2+2n)/n + 1/1000*(n^(3/2)))*log(n)
此功能的时间复杂度可能都是 O(n²*log(n)) and O(n^(3/2)*log(n))
这怎么可能？我认为这里的主导术语是n² (*log(n)),因此它应该O(n²*log(n))只是大O符号和时间复杂性措施感觉如此模糊
大O符号并不令人困惑.它定义了一个上限的算法的运行时间,因此,如果O(f(n))是一个有效的上限,每隔O(g(n))这样g(n) > f(n)明确是有效的,因为如果你的代码将在更短的运行,那么f(n)在不到,将肯定跑g(n).
在你的情况下,因为O(n^2 *log(n))支配O(n^(3/2) log(n)),它也是一个有效的上限,即使它不那么严格.此外,你可以说你的算法是O(n^3).问题是,哪一个Big O符号为我们提供了有关该算法的更多信息？显而易见的答案是较低的答案,这就是我们通常表明这一点的原因.
为了让事情变得简单:让我们说你可以在空中投球10米.然后,你可以说你不能超过10米,或者你可以说你不能超过15米.事实上,第一个是更严格的上限,不会使第二个成为错误的陈述.