问题描述
我正在尝试获取以下代码段的正确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:
我不明白的是: 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:
非正式地讲，这意味着当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 = O(n )，其中n = 1且c =2.因此，我们有了
So we have that n + n = O(n), with n = 1 and c = 2. Consequently, we have that
要真正做到这一点，我们需要证明如果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)= 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 ).要看到这一点，令P(n)=∑ (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
∑ (a n )≤∑ (a n )=(∑ (a ))n
∑(an) ≤ ∑(an) = (∑(a))n
所以P(n)= O(n ).
so P(n) = O(n).
希望这会有所帮助！
这篇关于循环中了解Big(O)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！