什么是多项式 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)) = {g(n) : ∃c>0 ∧ n0 ≥ 0 | g(n) ≤ c*f(n) ∀ n ≥ 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