理解循环中的大(O)

我试图获得以下代码片段的正确大0:

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-loop运行线性迭代次数，并且它包含一个线性循环，所以总复杂度是二次的，或者Θ(n²)。y环显然是Θ(n)这意味着x循环内的代码块是Θ(n + n²)。这整个块会被执行x循环的循环，它运行了n次。我们使用乘法法则得到Θ(n(n + n²)) = Θ(n² + n³)= Θ(n³)，即立方。

我不理解的是:怎么可能 O (n (n + n <一口> 2> 为 O (n <一口> 3> 这道数学题对吗?

这里所做的计算如下。当你说O(n(n + n²))时，这相当于说O(n² + n³)通过简单地将n分配到整个乘积中。

O(n² + n³) = O(n³)的原因是由大O表示法的形式定义得出的，即:

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

非正式地说，当n变得任意大时，f(n)的上界是g(n)的常数倍

为了正式证明n² + n³ = 0 (n³)，考虑任意n &g;1. 然后是

n² + n³ &l;n <一口> 3 + n <一口> 3 = 2 n <一口> 3

所以我们有n² + n³ = 0 (n³)其中n_{0 = 1且c = 2。因此，我们得到
O (n (n + n <一口> 2> 2> 3> 3> /blockquote>
要真正形式化，我们需要证明如果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')我们有
| f (n) |勒;c | g (n) |勒;C′′h(n)| = C x C′′h(n)|
所以f(n) = O(h(n))
更精确一点——在这里描述的算法的情况下，作者说运行时间是Θ(n³)，这比说运行时间是O(n³)更有力。θ;符号表明了一个紧密的渐近界，这意味着运行时以与n³相同的速率增长，而不仅仅是它从上面以n³的某个倍数为界。为了证明这一点，你还需要证明n³是0 (n² + n³)。我将把这个留给读者作为练习。: -)
更一般地说，如果你有任何k阶的多项式，使用类似的论证，该多项式是O(n^k)。看到这,让P (n) =总和;<子> i = 0 <一口> k (<子> n> <晚餐我>总和;<子> i = 0 <一口> k (<子> n> <晚餐我> i = 0 <一口> k (<子> n <一口> k> <我><一口> k (<子>))n <一口> k
so p (n) = O(n^k).
希望这对你有帮助!}

n (n + n <一口> 2> 2> 3

大0符号只关心n趋于无穷时的主导项，因此整个算法被认为是Θ(n³)。

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

由于n^3项优于n^2项，因此n^2项可以忽略不计，因此它是O(n^3)。

y循环可以被贴现，因为z循环(O(n) + O(n^2) -> O(n^2))忘掉算术吧。然后剩下三个嵌套循环，它们都遍历'seq'的整个长度，所以它是O(n^3)

相关内容

最新更新

热门标签：