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

Question

我目前是一名计算机科学本科生，正在学习数据结构课程。这学期，我们学习了大O表示法，在一项作业中，我们必须写出对数字1+2+3+...+n求和的大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 是执行的另一个操作的时间值，这意味着执行该操作的时间不断增加，并且您必须给出 Big-O这个操作顺序？

否则，当任务实际上只是对从 1 到 n 的所有数字求和并用大 O 表示法表示该时间时，当您采用循环所有元素的方法时，您的观点是正确的，即它是 O(n) ，并且使用 n*(n+1)/2 公式，您甚至可以得到 O(1)。