大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(n + 1)/ 2是对N个整数的连续序列求和的快速方法(从1开始).我认为你把一个算法与大哦符号混淆了!

如果你认为它是一个函数,那么这个函数的大复杂性就是O(1):

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

天真的实现将具有O(n)的大复杂性.

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 3

你感到困惑的复杂运行和大小(复杂性)结果.

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

但结果的复杂性,即"从1到n的总和"= n(n - 1)/ 2的大小是O(n ^ 2).

¹但是对于任意大的数字,这是简单的,因为添加大数字需要比添加小数字更长的时间.对于精确的运行时分析,您确实必须考虑结果的大小.然而,这通常与编程无关,甚至在纯粹的理论计算机科学中也是如此.在两个域中,求和数通常被认为是O(1)操作,除非域明确要求(即,当实现bignum库的操作时).