1到N累加求和的Big O为何有O(N)和O(N²)两种说法？

你看到的两个结论描述的是完全不同的度量对象，没有冲突，各自成立：

• 你写的代码时间复杂度为*O(N)*是正确的：你的实现用了1层从1到N的循环，每次循环内仅执行常数级的加法运算，总操作次数和N呈线性相关，因此时间复杂度是O(N)。
• Udemy课程提到的*O(N²)*描述的不是算法时间复杂度，而是数列求和结果本身的增长量级：等差数列1+2+…+N的求和公式为n*(n+1)/2，展开后最高阶项为n²，忽略低阶项和常数系数后，求和结果的增长量级就是O(N²)。

如果要实现时间复杂度为O(N²)的求和逻辑，你需要用嵌套循环的写法，每次循环仅加1，总操作次数恰好等于数列求和结果：

public void sum(int n){
 int sum =0;
 for(int i=1;i<=n;i++){
  // 内层循环执行i次，每次加1，等价于sum +=i
  for(int j=1;j<=i;j++){
    sum += 1;
  }
 }
 print(sum);
}

这个版本的总操作次数就是1+2+…+N，对应时间复杂度O(N²)，和课程里提到的量级对应。

内容的提问来源于stack exchange，提问作者WhyJava