是否有一种方法来做n个整数函数的和，将有O(n^2)?

Question

我想把这个简单的函数写成大写的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)