计算算法复杂性 - 混乱
我有以下代码片段：
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
sum++;
复杂度为 O(n^2)，但如果我想进一步了解内部循环复杂度，那么它会是 (n (n -1))/2 还是 (n-1)!？
I have the following code snippet:
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
sum++;
The complexity would be O(n^2), but if I want to dig a little more for the internal loop complexity then would it be (n (n-1))/2 or (n-1)!?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
是的，O(n^2)，但实际上 0+1+...+n-1=n(n-1)/2 = O(n^2)，绝对不是 (n-1)！
Yes, O(n^2), but actually 0+1+...+n-1=n(n-1)/2 = O(n^2), definitely not (n-1)!
由于大 O 表示法是上限，因此较小阶项 (-n) 和常数因子 (1/2) 都被删除（因为它们对于表示时间上限并不重要）以产生大- O 表示法，
O(n*n)更广为人知的是O(n^2)。Since big-O notation is an upper bound, the lesser order term (-n) and the constant factor (1/2) are both removed (because they aren't significant for representing the upper bound on time) to yield the big-O notation,
O(n*n)better known asO(n^2).您可以有一个运行时间
22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 步骤的算法，但它仍然是 O(n^2)。
找到比 O 更好的算法运行时间描述是一个悬而未决的问题。
You could have an algorithm that runs in time
22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 stepsAnd it would still be O(n^2).
It's an open problem to find a better description for algorithm running time than O.
就大 O 表示法而言，常量是无关紧要的。
Constants are irrelevant as far as big-O notation is concerned.
您计算出的
(n(n-1)/2)是代码的确切迭代次数。当询问时间复杂度是否大 O 时，您给出一个刚好足以表达所用时间的估计值。换句话说，您需要找到
n的THE SMALLESTpower，使得对于某些k (k>0),k * n^power将大于确切的迭代次数。在您的情况下，k恰好是1，power恰好是2。那么O(n^power)就是你的时间复杂度。What you have calculated
(n(n-1)/2)is the exact number of iterations for the code. When asked for time complexity in terms if big O, you give an estimate which is just big enough to express the time taken.In other words, you need to find
THE SMALLESTpowerofnsuch that for somek (k>0),k * n^powerwill be greater than the exact number of iterations. In your case,khappens to be1andpowerhappens to be2. ThenO(n^power)is your time complexity.首先，
(n-1)!表示(n-1)(n-2)...(2)(1)。这显然不是您想要的。如果计算实际的迭代次数，则为
0 + 1 + 2 + ... + (n-2) + (n-1)。请注意，总和中有 n 个项，我们可以将它们配对，使每对的平均值为 (n-1)/2 。 （将最高和最低、第二高和第二低等配对）如果n是奇数，则剩下一个无法配对，但方便的是，它的值也是 <代码>(n-1)/2。因此，您有n个项，所有项的平均值为(n-1)/2，因此总和为n(n-1)/2。现在，对于大 O 表示法，我们有多少次迭代并不重要——我们只想知道 n 非常大时的极限。请注意，我们的迭代次数可以写为
(1/2)n^2 - (1/2)n。对于非常大的n，n^2项比n项大得多，所以我们删除n< /代码> 术语。这样就只剩下(1/2)n^2，但大 O 表示法的另一个规则是我们不关心常数因子，所以我们只写它是 O(n^2 ）。First of all,
(n-1)!means(n-1)(n-2)...(2)(1). This is clearly not what you want here.If you count the actual number of iterations it's
0 + 1 + 2 + ... + (n-2) + (n-1). Note that there arenterms in the sum, and that we can pair them off in a way such that the average value of each pair is(n-1)/2. (Pair the highest and lowest, the second highest and second lowest, etc.) Ifnis odd, you'll have one left over that can't be paired, but conveniently its value is also(n-1)/2. Thus you haventerms and the average of all terms is(n-1)/2, so the total sum isn(n-1)/2.Now, for big O notation it doesn't matter exactly how many iterations we have -- we just want to know the limit when
nis very large. Note that our number of iterations can be written as(1/2)n^2 - (1/2)n. For very largen, then^2term is way, way bigger than thenterm, so we drop thenterm. That just leaves us with(1/2)n^2, but another rule of big O notation is we don't care about the constant factor, so we just write that it's O(n^2).