帮助计算大O.

Question

我试图获取以下代码片段的正确Big-O:

s = 0
for x in seq:
  for y in seq:
    s += x*y
  for z in seq:
    for w in seq:
      s += x-w

根据我从(Python算法)得到这个例子的书,他们解释如下:

z循环运行一系列线性迭代,并且它包含一个线性循环,因此总复杂度为二次方或Θ(n ²).y环显然是Θ(n).这意味着x循环内的代码块是Θ(n + n ²).整个块执行x循环的每一轮,运行n次.我们使用乘法规则得到Θ(n(n + n ²))=Θ(n ² + n ³)=Θ(n ³),即立方.

我不明白的是:O(n(n + n ²))怎么会变成O(n ³)？数学是否正确？

Answer 1

这里完成的数学运算如下.当你说O(n(n + n ²))时,这相当于通过简单地在整个产品中分配n 来说O(n ² + n ³).

O(n ² + n ³)= O(n ³)的原因来自big-O表示法的正式定义,如下所示:

函数f(N)= O(G(N))当且仅当存在常数n ₀和c,使得对于任意的n≥Ñ ₀,| F(N)| ≤c| g(n)|.

非正式地说,这表示当n变得任意大时,f(n)从上面以g(n)的常数倍为界.

为了正式证明n ² + n ³是O(n ³),考虑任何n≥1.然后我们得到

Ñ ² + N ³ ≤Ñ ³ + N ³ = 2 ³

所以我们得到n ² + n ³ = O(n ³),其中n ₀ = 1且c = 2.因此,我们有

O(n(n + n ²))= O(n ² + n ³)= O(n ³).

为了真正形式化,我们需要证明,如果f(n)= O(g(n))和g(n)= O(h(n)),那么f(n)= O(h( N)).让我们来看看这个证明.如果F(N)= O(G(N)),有常数n ₀和c,使得对于n≥Ñ ₀,| F(N)| ≤c| g(n)|.类似地,由于G(N)= O(H(N)),有常数n ' ₀,C',使得对于n≥N ' ₀,G(N)≤C' | H(N)|.所以这意味着对于任何n≥max(c,c'),我们都有

| F(N)| ≤c| g(n)| ≤c| c'h(n)| = cxc'| h(n)|

所以f(n)= O(h(n)).

为了更精确一些 - 在这里描述的算法的情况下,作者说运行时是Θ(n ³),这比运行时为O(n ³)的结果更强.Θ符号表示紧密的渐近界,意味着运行时以与n ³相同的速率增长,而不仅仅是它从上面以n ^3的某个倍数为界.为了证明这一点,你还需要证明n ³是O(n ² + n ³).我会将此作为练习留给读者.:-)

更一般地说,如果你有任何 k阶多项式,那么多项式是O(n ^k),使用类似的参数.为了看到这一点,设P(n)=Σi _{= 0} ^k(a _i n ⁱ).那么,对于任何n≥1,我们都有

Σi _{= 0} ^k(a _i n ⁱ)≤Σi _{= 0} ^k(a _i n ^k)=(Σi _{= 0} ^k(a _i))n ^k

所以P(n)= O(n ^k).

希望这可以帮助!

Answer 2

O(n(n+n^2)) = O(n^2 + n^3)

由于该n^3术语在该术语中占主导地位n^2,因此该n^2术语可以忽略不计,因此可以忽略不计O(n^3).

Answer 3

n(n + n ²)== n ² + n ³

由于n变为无穷大,Big-O表示法仅关注主导项,因此整个算法被认为是Θ(n ³).