什么是多项式 f（n） = n/20 的次数

Question

如果一个算法执行一个语句，它是n/2次，那么为什么O等于O（n）。因为视频解释说这是因为多项式的次数。请解释。

for(int i =0;i<n;i=i+2){

sout(n) ---- This statemet can be print n/2 times

}

f(n) = n/2  then O(n)

Answer 1

简单来说，虽然语句会打印时间，但它仍然与 .n/2n对于 n=10，它将打印 5 次。对于 n=50，它将打印 25 次。对于 n=100，它将打印 50 次。请注意线性关系。该因子仅乘以 。它是一种线性关系，表示线性关系，并且不关心常量（在本例中）。甚至会是.1/2nO(n)1/2f(n) = n/3O(n)

Answer 2

是的，正如Aoerz已经说过的那样，要理解你的问题，你应该理解O符号的含义。以数学方式：O(f(n))&nbsp;=&nbsp;{g(n)&nbsp;:&nbsp;∃c>0&nbsp;∧&nbsp;n0&nbsp;≥&nbsp;0&nbsp;|&nbsp;g(n)&nbsp;≤&nbsp;c*f(n)&nbsp;∀&nbsp;n&nbsp;≥&nbsp;n0}所以（在某个和一个常量之后g(n) ∈ O(f(n)) if g(n) ≤ c*f(n)n0c)用简单的话来说，可以把它想象成一个非常大的数字。所有其他因素有多重要？那么，唯一真正重要的主要因素是什么呢？n示例：（尝试一下，您会发现这已经足够了）f(n) = n^3 + 300*n +5 --> f(n) ∈ O(n^3)n=100