1+2+3+...+n的Big-O表示法

Question

1+2+3+...+n的Big-O表示法

5

我目前是一名CS本科生，正在学习数据结构课程。在这个学期中，我们学习了大O符号，其中有一个作业要求我们写出计算1+2+3+…+n的大O符号。我认为，在最简单的方法中，您会循环从1到n，并在每次迭代中将i添加到总和中，因此看起来这将是O(n)时间复杂度。

我也知道，可以将这个特定的求和表达为（n（n + 1））/ 2，以更直接的方式获得答案。

我的教授坚持认为，在这两种情况下，时间复杂度都是O（n ^ 2），我已经通过电子邮件与他来往希望得到更好的解释，但他基本上每次都发同样的回复。

我觉得我必须首先不理解大O符号的目的。即使我在程序中实现这两种找到总和的方法并测量执行时间，循环方法的时间似乎基于n的大小呈线性增长，而在第二种方法中，无论n有多大，所需的时间都相同，因为在这种情况下没有迭代发生。

请问有人能帮助我理解为什么这仍然是O(n ^ 2)吗？

- sode

1

这是他告诉我答案取决于我们执行的操作数量，对于(n(n+1)/2)的情况，我只看到3个操作。如果他能花时间适当地解释一下，而不是无论我问多少次都回复“答案是O(n^2)，因为它是(n(n+1))/2”。 - sode

4个回答

1

在像这样的Java示例中。

int n = 1000;
int sum = 0;

// iterating n times
for (int i = 1; i <= n; i++) {
    // just a basic operation, so no extra complexity here
    sum += i;
}

这个加法被调用了n次，所以整个代码的时间复杂度为O(1) * n = O(n)。

如果你的问题没有遗漏任何信息，O(n)将是任务的正确答案。

无论如何，教授是正确的的可能性很大 ;-)

O(n * (n + 1) / 2) = O(n / 2) * O((n + 1) / 2) = O(n) * O(n + 1) = O(n) * O(n) = O(n * n) = O(n^2)

- deHaar

我现在真的不知道该怎么想了，他最近给我的回复是“每次迭代需要 i 次操作，所以总共我们有 n(n+1)/2 次操作”，但我越看越困惑，因为按照这个公式，好像并没有发生迭代的过程？ - sode

很想知道每一次迭代中发生了什么（教授正在考虑）……但愿他不是指对从1到n的值进行n次求和… - deHaar

我不是完全确定，而且从他那里得到除了O(n^2)以外的任何答复似乎都很不可能。 - sode

不解释地给出正确答案是一种非常奇怪的教学方式...然后给出正确答案，通过作业并与他人讨论。我认为除了与不同的教授交谈之外，没有其他选择。 - deHaar

1

使用公式(n * (n + 1))/2求输入的总和，复杂度为O(1)。为什么在那里使用大O符号表示法？ - kriss

我真的不确定，那只是我们作业上一个多项选择题，如果我答对了，就能让我得到A而不是B。我们的老师真的不怎么样。他整节课都在念别人的幻灯片，每个幻灯片自己读完还要花30秒才开始讲话。他从来没有明确他对我们项目的期望，很多学生显然在这门课上挣扎，我听说教授几乎没什么帮助，现在我也亲身感受到了。 - sode

0

这是不是一个误解，1、2、...、n是另一个操作的时间值，执行该操作的时间不断增加，你必须为这个操作序列给出Big-O？

否则，如果任务只是将所有数字从1加到n并用Big-O表示时间，那么您的观点是正确的，当您采用循环所有元素的方法时，它是O(n)，使用n*(n+1)/2公式甚至可以得到O(1)。

- Stefan Illner

感谢您的快速回复，问题直接从作业中提取：“1+2+3+...+n的正确的大O表达式是哪个？” A. O(log n) B. O(n) C. O(n log n) D. O(n²)。因此，甚至没有常数时间的选项，这使得他一开始提出那个公式变得奇怪。 - sode

好的，我想那么你的教授是正确的。我不是一个以英语为母语的人，但问题不在于为计算该总和所需的时间给出大O表达式，而是1+2+...+n是值，取决于n。正如您正确指出的那样，这是n*(n+1)/2，即（n^2）/2 + n/2，因此O(n^2)是正确答案。 - Stefan Illner

可能是这样，但他一直提到操作和迭代次数的数量，但如果他只是指结果本身，那么他提到这些事情只会让它更加混乱。我知道他不是自己提出这个问题的，因为你可以在谷歌上找到它，而且他也不是以英语为母语的人，所以这可能是我们双方的误解。 - sode

0

如果您逐个迭代数字进行求和，则答案为O(n)。

如果您直接使用求和公式，则答案为O(1)。

- displayName

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AlexP · Accepted Answer

你计算的值是错误的。

正如你在评论中指出的，问题并不是询问求和的时间复杂度；问题是求和本身的阶数。而 1 + 2 + ... + n 的阶数确实是 O(n²)。