帮助计算大O [英] Help calculating Big O

问题描述

我试图得到正确的大O以下code代码段：

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循环运行的迭代线性数，和   它包含了一个线状回路，所以总的复杂性有二次，或Θ（正 ² ）。的y环路显然Θ（n）的。   这意味着在x循环内的code嵌段是Θ（N + N ² ）。这整个区块为每个执行   轮的x循环，这是运行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 ³ ）从大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））当且仅当存在常数ñ<子> 0 和C使得对任意n＆GE; ñ<子> 0 ，| 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＆GE; 1。然后我们有

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

N ² + N ³ ＆乐; ñ ³ + N ³ = 2 ³

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）），有常数ñ<子> 0 和c，使得对于n＆GE; ñ<子> 0 ，| F（N）|与乐; C | G（N）|。类似地，由于G（N）= 0（H（N）），有常量N'<子> 0 ，c'的，使得对于n＆葛; N'<子> 0 ，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中√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)).

要多一点precise - 在这里所描述的算法的情况下，作者们说，运行时间和西塔（N ³ ），这是一种强大的结果比说，运行时间为O（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阶多项式，即多项式为O（n ^K ），采用了类似的说法。看到这一点，令P（n）=总和; <子> I = 0 ^K （A <子>我 N ^我） 。然后，对于任意n＆GE; 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 <子>我 N ^我）与乐; ＆总和; <子> I = 0 ^K （A <子>我 N ^K ）=（总和; <子> I = 0 ^K （A <子>我））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).

希望这有助于！

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