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

我目前是一名 CS 本科生，就读于数据结构课程。在学期中，我们学习了大 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）吗？

标签： time-complexitybig-o

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

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