帮助计算大O

扫码查看
本文介绍了帮助计算大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 )  =Θ(正),即,立方

我不明白的是:怎么可能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))当且仅当存在常数ñ,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)= 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 ),采用了类似的说法。看到这一点,令P(n)=总和; I = 0 (A 我 N ) 。然后,对于任意n≥ 1,我们有

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

&总和; I = 0 (A 我 N )与乐; &总和; I = 0 (A 我 N )=(总和; I = 0 (A 我))N

∑(an) ≤ ∑(an) = (∑(a))n

因此​​P(N)=为O(n )。

so P(n) = O(n).

希望这有助于!

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

08-03 18:31
查看更多