为什么这个算法的大O复杂度是O(n^2)？

Question

我知道这个算法的大O复杂度是O(n^2)，但我不明白为什么。

int sum = 0; 
int i = 1; j = n * n; 
while (i++ < j--) 
  sum++;

虽然我们一开始设置了j = n * n，但在每次迭代中我们将i增加而将j减少，所以最终的迭代次数应该比n*n要少得多，对吗？

- Omar N

---

是的，它小于 n*n，但迭代次数与 n*n 成比例。这就是大O符号所表示的意思。 - nicola

无论你将i增加1、5还是10,000，将n翻倍仍会使运行时间增加4倍，这是O(n^2)算法的特征。 - chepner

提示: 在此循环结束时，sum == n*n / 2。 - geometrian

明确一点，大O复杂度也可以是O(n^3)，O(e^n)，和O(n!^n!)。 - djechlin

大O表示法提供上界，但并不一定是“紧”的。 - djechlin

Answer 1

每次迭代中，你增加i并减少j，这相当于将i增加2。因此，总迭代次数为n^2 / 2，仍然是O(n^2)。

- Miljen Mikic

---

换句话说，i 增加是线性的，而 j 增加是二次的。二次增长的速度比线性增长更快，这就是为什么时间复杂度是 O(n^2)。 - jean

@jean i的初始值是一个与n无关的常量。因此，你不应该那样比较i和j。 - Dmytro Shevchenko

是的，我可以这么做，因为我比较的不是变量设置的值，而是它们如何控制迭代。请注意，一个变量递增，另一个变量递减直到它们“相遇”。i从一个常量开始线性增长，j从二次方开始递增但线性递减。您可以通过将j设置为相同的常量并增加它直到i+j < n^2来轻松保持逻辑。在问题中编写的递减j和while条件只是为了检查您是否正在关注逻辑。 - jean

Answer 2

大O复杂度忽略系数。例如：O(n)、O(2n)和O(1000n)都是相同的O(n)运行时间。同样，O(n^2)和O(0.5n^2)都是O(n^2)的运行时间。

在您的情况下，您基本上每次通过循环将计数器增加2（因为j--与i++具有相同的效果）。因此，您的运行时间是O(0.5n^2)，但当您移除系数时，这与O(n^2)相同。

- Ben Rubin

---

这与系数在这种情况下无关。 O(0.5n^2) 等于 O(0.5n^3)。 - djechlin

@djechlin，你似乎花了很多时间来检查这个问题并“教育”人们。不妨再花费几秒钟来更好地表达你的评论建议？此外，在O符号空间中，将二次和三次时间复杂度等同起来是非常错误的。请参见https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities以获取列表。 - marknuzz

@djechlin Nuzzolilo是正确的。O(n^2)和O(n^3)之间确实有区别。在大O符号中，系数并不重要，但幂次却很重要。不要混淆系数和常数。 - Ben Rubin

在您扩展解释的背景下，将O(n^2) = O(n^3)视为相等是正确的，但是该主题线路顶部的原始一行陈述并没有很好地解释清楚。即使您是房间中最厉害的人，但如果无法清晰表达您的想法，那么您的知识也就没什么用了。如果您认为每个持不同观点的人都是巨魔，那么您就会失去一个重要的外部学习资源，并且如果这样做，您不会长期保持顶尖大佬的地位。这只是一些值得思考的食物。 - marknuzz

@djechlin所说的O(n²)不是O(n³)，但它是O(n³)的子集。 - Paul

Answer 3

您将恰好进行 n*n/2 次循环迭代（如果 n 是奇数则为(n*n-1)/2）。

在大 O 记号中，我们有 O((n*n-1)/2) = O(n*n/2) = O(n*n)，因为常数因素“不计入”。

- m3tikn0b

Answer 4

您的算法等同于

while (i += 2 < n*n) 
  ...

这是 O(n^2/2) ，与 O(n^2) 相同，因为大O复杂度不关心常数。

- Salvador Dali

---

最简单的答案 :) - AVI

Answer 5

设m为迭代次数，则有：

i+m = n^2 - m

化简得：

m = (n^2-i)/2

在大O符号表示中，这意味着复杂度为O(n^2)。

- Ujjwal Aryan

Answer 6

是的，这个算法的复杂度为O(n^2)。

为了计算复杂度，我们有一个复杂度表：

O(1) O(log n) O(n) O(n log n)
O(n²) O(n^a) O(a^n) O(n!)

每一行代表一组算法。一个在O(1)中的算法也在O(n)和O(n^2)中，等等。但反过来则不然。因此，你的算法实现了n*n/2句话。

O(n) < O(nlogn) < O(n*n/2) < O(n²)

所以，包括你的算法复杂度的算法集合是O(n²)，因为O(n)和O(nlogn)更小。

例如： 当n=100时，求和为5000。 => 100 O(n) < 200 O(n·logn) < 5000 (n*n/2) < 10000(n^2)

对我的英语表示抱歉。

- Francisco Manuel Garca Botella

Answer 7

尽管我们在开始时将j = n * n设置，但我们在每次迭代中递增i并递减j，所以迭代次数的结果不应该比n * n少得多吗？

是的！这就是为什么它是O（n ^ 2）。按照同样的逻辑，它比n * n * n少得多，这使其成为O（n ^ 3）。甚至根据类似的逻辑，它是O（6 ^ n）。

大O给出了有关上界的信息。

我相信您正在尝试询问为什么复杂度是theta（n）或omega（n），但如果您只是想了解big-O是什么，您确实需要首先了解它主要提供函数的上界。

- djechlin

---

成功地指出了“大O表示法提供了关于上限的信息”。但是O（6 ^ n）是什么意思？这是一个幂函数，而不是指数函数。 - aaaarrgh

@aaaarrgh 6^n的增长速度比任何多项式都要快。因此，任何O(n^c)的算法，其中c为常数，也将属于O(6^n)。 - Taemyr

@djechlin 看看 XY 问题，并意识到 OP 正试图了解为什么 O(n^2) 是最窄的上界。 - Taemyr

Theta比大O符号更难处理。因此，我认为对于OP的问题，严谨的纠正不应该是“你应该问为什么算法是Theta（n ^ 2）”，而是“你应该问为什么O（n ^ 2）是最紧密的上界”。 - Taemyr

在高级计算机科学课程中，您正在谈论Big-O的含义，其中您区分了Big-O、Big-Theta和Big-Omega。在现实世界中，程序员通常说“Big-O”，但实际上他们可能是指的Big-Theta。StackOverflow主要由在现实世界中工作的程序员组成，而不是研究生。这就是为什么每个人都在与您争论的原因。 :) - Kip