algorithm - 用大哦符号计算算法的时间复杂度

Question

假设算法的时间复杂度为O(n^2) .现在我知道了

f(n) = O(g(n)) , if c1*g(n)<=f(n)<=c2*g(n) for all n>=n0 

Constants c1 and c2 are positive real numbers
n0 = non negative integer    
f(n),g(n) = non negative functions of non negative arguments  

在这里g(n) = n^2并假设 f(n) = n(n-1) .我拿c1 = 0 and c2 = 1 .

所以 0*(n^2) <= n(n-1) <= 1(n^2)其中 n>=1

但是n>=0也满足条件

但是我们一般没有 n = 0

那我写什么呢 n>=0 或 n>=1

Answer 1

您应该阅读声明的方式是:

函数 f(n) 是 O(g(n)) 如果在某个点之后 n0 f( n) 保持在g(n)附近的相对区间内，介于c1*g(n)和c2*g(n)之间。

因此，只要存在 n0、c1 和 c2，您就可以对任何关系这样说。因此 n = 0 并不重要。 n=1 也没有。重要的是在某一点之后条件成立。您可以用 n0 = 42 证明条件成立并得出 f(n)=n(n-1) 是 O(n^2) 的结论。

对于一些更复杂的函数，f(n) 对于较低的值会表现得很奇怪，因此忽略它们并选择一些较高的值可能是有意义的。无论 n0 有多大，只要您能找到一个满足条件的就没问题。