循环中了解Big(O) [英] Understanding Big(O) in loops

问题描述

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

I am trying to get the correct Big-O of the following code snippet:

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算法)那里得到的这个例子的书，他们这样解释:

According to the book I got this example from (Python Algorithms), they explain it like this:

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

The z-loop is run for a linear number of iterations, and it contains a linear loop, so the total complexity there is quadratic, or Θ(n²). The y-loop is clearly Θ(n). This means that the code block inside the x-loop is Θ(n + n²). This entire block is executed for each round of the x-loop, which is run n times. We use our multiplication rule and get Θ(n(n + n²)) = Θ(n² + n³) = Θ(n³), that is, cubic.

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

What I don't understand is: how could O(n(n+n²)) become O(n³). Is the math correct?

推荐答案

此处进行的数学运算如下.当您说O(n(n + n ² ))时，这相当于通过简单地分配O(n ² + n ³ )产品中的n.

The math being done here is as follows. When you say O(n(n + n²)), that's equivalent to saying O(n² + n³) by simply distributing the n throughout the product.

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

The reason that O(n² + n³) = O(n³) follows from the formal definition of big-O notation, which is as follows:

一个函数f(n)= O(g(n))，如果存在常数n ₀ 和c，则对于任何n≥n ₀ ，| f(n)|≤c | g(n)|.

A function f(n) = O(g(n)) iff there exists constants n₀ and c such that for any n ≥ n₀, |f(n)| ≤ c|g(n)|.

非正式地讲，这意味着当n变得任意大时，f(n)从上方被g(n)的常数倍限制.

Informally, this says that as n gets arbitrary large, f(n) is bounded from above by a constant multiple of g(n).

要正式证明n ² + n ³ 为O(n ³ )，请考虑任意n≥.1.然后我们有

To formally prove that n² + n³ is O(n³), consider any n ≥ 1. Then we have that

n ² + n ³ ≤n ³ + n ³ = 2n ³

n² + n³ ≤ n³ + n³ = 2n³

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

So we have that n² + n³ = O(n³), with n₀ = 1 and c = 2. Consequently, we have that

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

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≥n ₀ ，| f(n)|≤c | g(n)|.类似地，由于g(n)= O(h(n))，因此存在常数n' ₀ ，c'，使得对于n≥n' ₀ ，g(n)≤c'| h(n)|.因此，这意味着对于任何n≥max(c，c')，我们有

To be truly formal about this, we would need to show that if f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)). Let's walk through a proof of this. If f(n) = O(g(n)), there are constants n₀ and c such that for n ≥ n₀, |f(n)| ≤ c|g(n)|. Similarly, since g(n) = O(h(n)), there are constants n'₀, c' such that for n ≥ n'₀, g(n) ≤ c'|h(n)|. So this means that for any n ≥ max(c, c'), we have that

| f(n)|≤c | g(n)|≤c | c'h(n)|= c x c'| h(n)|

|f(n)| ≤ c|g(n)| ≤ c|c'h(n)| = c x c' |h(n)|

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

And so f(n) = O(h(n)).

更精确一点-对于此处描述的算法，作者说运行时为Θ(n ³ )，比说运行时间为O(n ³ ).Θ符号表示紧密的渐近边界，这意味着运行时以与n ³ 相同的速率增长，而不仅仅是它从上方被n ³ 的某个倍数所限制.为了证明这一点，您还需要证明n ³ 为O(n ² + n ³ ).我会将其作为练习留给读者.:-)

To be a bit more precise - in the case of the algorithm described here, the authors are saying that the runtime is Θ(n³), which is a stronger result than saying that the runtime is O(n³). Θ notation indicates a tight asymptotic bound, meaning that the runtime grows at the same rate as n³, not just that it is bounded from above by some multiple of n³. To prove this, you would also need to show that n³ is O(n² + n³). I'll leave this as an exercise to the reader. :-)

更一般而言，如果您具有k阶的 any 多项式，则使用类似的参数，该多项式为O(n ^k ).要看到这一点，令P(n)=∑ _{i = 0} ^k (a _i n ⁱ ).然后，对于任何n≥1，我们有

More generally, if you have any polynomial of order k, that polynomial is O(n^k) using a similar argument. To see this, let P(n) = ∑_i=0^k(a_inⁱ). Then, for any n ≥ 1, we have that

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

∑_i=0^k(a_inⁱ) ≤ ∑_i=0^k(a_in^k) = (∑_i=0^k(a_i))n^k

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

so P(n) = O(n^k).

希望这会有所帮助！

这篇关于循环中了解Big(O)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！