大O，对一系列n 个数字求和的复杂度是多少？

Question

我一直认为：1 + 2 + 3 + ... + n 的复杂度

是 O(n)，对两个 n × n 矩阵求和将是 O(n^2)。

但今天我从一本教科书上读到，“根据前n个整数之和的公式，这是n(n+1)/2”，然后这样：(1/2)n^2 + (1/2) n，因此 O(n^2)。

我在这里缺少什么？

Answer 1

大 O 表示法可用于确定任何的增长率功能。

在这种情况下，这本书似乎不是在讨论计算值的时间复杂度，而是在讨论值本身。 n(n+1)/2 是 O(n^2)。

Answer 2

您混淆了运行时的复杂性和结果的大小（复杂性）。

求和的运行时间，一个接一个，前n个连续的数字确实是O(n) .¹

但是结果的复杂度，即“从 1 到 n 的总和”的大小 = n(n< /i> – 1) / 2 是O(n ^ 2)。

---

¹ 但是对于任意大的数字来说，这很简单，因为添加大数字比添加小数字需要更长的时间。对于精确的运行时分析，您确实必须考虑结果的大小。然而，这通常与编程无关，甚至与纯理论计算机科学无关。在这两个领域中，数字求和通常被视为O(1) 运算，除非该领域明确要求（即在为bignum 库实现运算时）。

Answer 3

n(n+1)/2 是对 N 个整数（从 1 开始）的连续序列求和的快速方法。我认为您将算法与大哦符号混淆了！

如果您将其视为一个函数，那么该函数的 big-oh 复杂度为 O(1)：

public int sum_of_first_n_integers(int n) {
  return (n * (n+1))/2;
}

简单的实现将具有 O(n) 的 big-oh 复杂度。

public int sum_of_first_n_integers(int n) {
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += n;
  }
  return sum;
}

即使仅查看单个 n×n 矩阵的每个单元也是 O(n^2)，因为该矩阵有 n^2 个单元。

Answer 4

实际上并不存在问题的复杂性，而是算法的复杂性。

在您的情况下，如果您选择迭代所有数字，则复杂性实际上是O(n)。

但这不是最有效的算法。更有效的方法是应用公式 - n*(n+1)/2，该公式是常数，因此复杂度为 O(1)。

Answer 5

所以我的猜测是，这实际上是对破解编码面试的引用，其中有一段关于 StringBuffer 实现的内容：

在每次串联时，都会创建字符串的新副本，并且
两个字符串被逐个字符地复制。第一个
迭代需要我们复制x个字符。第二次迭代
需要复制 2x 个字符。第三次迭代需要 3x，并且
很快。因此，总时间为O(x + 2x + ... + nx)。这减少了
到O(xn²)。 （为什么不是O(xnⁿ)？因为1 + 2 + ... n等于n(n+1)/2
或者，O(n²)。）

无论出于何种原因，我在第一次通读时也发现这有点令人困惑。需要注意的重要一点是，n 正在与 n 相乘，或者换句话说，n² 正在发生，并且占主导地位。这就是为什么最终 O(xn²) 只是 O(n²) —— x 有点转移注意力。

Answer 6

您有一个不依赖于相加数字数量的公式，因此它是一个恒定时间算法，即 O(1)。

如果每次将每个数字相加，那么它确实是 O(n)。公式是捷径；这是一种不同的、更有效的算法。当添加的数字均为 1..n 时，该快捷方式有效。如果您有不连续的数字序列，则快捷公式不起作用，您必须返回到一对一算法。

不过，这些都不适用于数字矩阵。要添加两个矩阵，它仍然是 O(n^2)，因为您要添加 n^2 个不同的数字对来获得包含 n^2 个结果的矩阵。

Answer 7

对 N 个任意整数求和与对 N 个连续整数求和之间存在差异。对于 1+2+3+4+...+N，您可以利用它们可以分成具有共同总和的对的事实，例如 1+N = 2+(N-1) = 3+( N-2) = ... = N + 1。所以这是 N+1, N/2 次。 （如果有奇数，其中一个将不成对，但稍加努力，您就会发现在这种情况下相同的公式成立。）

但这不是 O(N^2)。这只是一个使用 N^2 的公式，实际上是 O(1)。 O(N^2) 意味着（粗略地）对于较大的 N，计算它的步骤数会像 N^2 一样增长。在这种情况下，无论 N 如何，步骤数都是相同的。

Answer 8

添加前 n 个数字：

考虑算法：

Series_Add(n)

   return n*(n+1)/2

该算法确实运行在 O(|n|^2) 中，其中 |n|是 n 的长度（位）而不是幅度，因为 2 个数字（k 位中的一个和 l 位中的另一个）的乘法需要 O(k*l) 时间。

小心

考虑这个算法：

Series_Add_pseudo(n):
   sum=0   
   for i= 1 to n:
      sum += i
   return sum

这是一种简单的方法，您可以假设该算法以线性时间或通常以多项式时间运行。事实并非如此。

n 的输入表示（长度）是 O(logn) 位（除一元之外的任何 n 元编码），并且算法（尽管它在幅度上线性运行）它以指数方式运行（2^ logn) 输入的长度。
这实际上是伪多项式算法的情况。它看起来是多项式，但事实并非如此。

您甚至可以在 python（或任何编程语言）中尝试使用中等长度的数字，例如 200 位。

应用第一个算法，结果在一瞬间就出来了，而应用第二个算法，你必须等待一个世纪......

Answer 9

1+2+3+...+n 始终小于 n+n+n...+nn 次。你可以将这个 n+n+..+n 重写为 n*n。

f(n) = O(g(n)) 如果存在正整数 n0 和正整数
常数 c，使得 f(n) ≤ c * g(n) ∀ n ≥ n0

因为 Big-Oh 表示函数的上限，其中函数 f(n) 是直到 n 的自然数之和。

现在，谈论时间复杂度，对于较小的数字，加法应该是恒定的工作量。但 n 的大小可能非常巨大；你不能否认这个可能性。

当 n 很大时，添加整数可能会花费线性时间。。所以你可以说加法是 O(n) 操作并且你正在添加 n 个项目。因此仅此一项就可以使其成为 O(n^2) 。当然，并不总是需要 n^2 时间，但当 n 很大时这是最坏的情况。 （上限，还记得吗？）

---

现在，假设您直接尝试使用 n(n+1)/2 来实现它。只要一乘一除，这应该是一个常量运算吧？
不。

使用位数的自然大小度量，使用长乘法将两个 n 位数字相乘的时间复杂度为 θ(n^2)。当在软件中实现时，长乘法算法必须处理加法期间的溢出，这可能是昂贵的。 维基百科

这又让我们的时间复杂度为 O(n^2)。

Answer 10

它等价于 BigO(n^2)，因为它等价于 (n^2 + n) / 2 并且在 BigO 中你忽略了常数，所以即使 n 的平方除以 2，你仍然有指数增长的正方形。

考虑一下 O(n) 和 O(n/2) 吗？同样，我们也不区分两者，对于较小的 n，O(n/2) 只是 O(n)，但增长率仍然是线性的。

这意味着随着 n 的增加，如果您要在图表上绘制操作数，您会看到一条 ^2 曲线出现。

您已经可以看到：

when n = 2 you get 3
when n = 3 you get 6
when n = 4 you get 10
when n = 5 you get 15
when n = 6 you get 21

如果您像我在这里那样绘制它：

您会看到曲线是与 n^2 类似，每个 y 处的数字都会较小，但曲线与之相似。因此我们说大小是相同的，因为随着 n 变大，它的时间复杂度也会像 n^2 一样增长。

Answer 11

n 个自然级数之和的答案可以用两种方法找到。第一种方法是将循环中的所有数字相加。在这种情况下，算法是线性的，代码将类似于

 int sum = 0;
     for (int i = 1; i <= n; i++) {
     sum += n;
   }
 return sum;

1+2+3+4+......+n。在这种情况下，算法的复杂度计算为执行加法运算的次数，即 O(n)。

求n个自然数级数之和答案的第二种方法是最直接的公式n*(n+1)/2。该公式使用乘法而不是重复加法。乘法运算没有线性时间复杂度。有多种乘法算法可供选择，其时间复杂度从 O(N^1.45) 到 O(N^2) 不等。因此，在乘法的情况下，时间复杂度取决于处理器的架构。但出于分析目的，乘法的时间复杂度被视为 O(N^2)。因此，当使用第二种方法求和时，时间复杂度将为 O(N^2)。

这里的乘法运算与加法运算不同。如果任何人具有计算机组织学科的知识，那么他可以轻松理解乘法和加法运算的内部工作原理。乘法电路比加法器电路更复杂，并且需要比加法器电路更长的时间来计算结果。所以级数之和的时间复杂度不可能是常数。