time-complexity - 1+2+3+...+n 的大 O 表示法

Question

我目前是一名 CS 本科生，就读于数据结构类(class)。在学期中，我们学习了 big-O 表示法，在一项作业中，我们不得不写出对数字 1+2+3+...+n 求和的 big-O 表示法。我认为，在最简单的方法中，您将从 1 循环到 n，并在每次迭代中将 i 添加到总和中，因此看起来这将是 O(n) 时间。

我也知道这个特定的总和可以表示为 (n(n+1))/2 作为接收答案的更直接方式。

我的教授坚持认为，在这两种情况下，时间复杂度都是 O(n^2)，我一直在给他发电子邮件，希望得到更好的解释，但他基本上每次都发送相同的回复。

我觉得我首先一定是误解了 big-O 的目的。即使我实现了这两种在程序中求和并计时的方法，循环方法的时间似乎根据 n 的大小线性增加，而在第二种方法中，它需要相同的时间没有无论 n 有多大，因为在这种情况下没有发生迭代。

有人可以帮我理解为什么这仍然是 O(n^2)？

Answer 1

您正在计算错误值的顺序。

正如您在评论中指出的，这个问题不问求和的时间复杂度是多少；问题是求和本身的顺序是什么。确实 1 +
2 + ... + n 是 O(n²)。