有没有办法求出 n 个整数求和的复杂度为 O(n^2) 的函数？

Question

我想以一种使它的大 O 表示法成为 O(n^2) 的方式编写这个简单的函数，我怎样才能做到这一点？

int getSum(int n){ 
int sum = (n*(n+1))/2; 
return sum;

有什么想法吗？

Answer 1

我不太确定你为什么要这个，但你可以用两个嵌套循环来完成：

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

这运行 1+2+3+...+n 次，简化为 (n^2+n)/2，因此 O(n^2)

有没有办法求出 n 个整数求和的复杂度为 O(n^2) 的函数？

Is there a way to do the sum of the n integers function that would have O(n^2)?

big-o