这个函数的运行时间是多少？为什么？

Question

有很多类似的问题，但我还没有看到这种变化

void myFunc(int n) {
int sum;
int i, j;
    sum = 0;
    for(i = 1; i <= n; i += 1){
        for(j = 1; j <= n; j += 1){
            sum += i;
} }
    for(i = 1; i <= sum; i += 1){
        cout<<”func2 is awesome!”<<endl;
    }
 }

Answer 1

第一个嵌套 for 循环时间复杂度为

O(n^2)

。从 for 循环得到的

sum

上面的时间复杂度是

n * n * (n + 1) / 2

所以最后一个 for 循环是

O(n * n * (n + 1) / 2) -> O(n^3)

所以总时间复杂度是

O(n^2 + n^3) -> O(n^3)