问题描述

一个关于时间复杂度问题

 for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
    // do something
    }
}

这种我不太清楚，外层循环是n,但是内循环次数是1到n，所以这种算是O(n^2)吗。谢谢

解决方案

一共执行了(1+2+3+...+n-1+n)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以时间复杂度也是O(n^2)

解决方案二：

当n=5时
i:0 1 2 3 4 5

j: 0 0,1 0,1,2 0,1,2,3 0,1,2,3,4

解决方案三：

对，就是O(n^2)

解决方案四：

算O(n^2)吧，1+2+3+4+5+.......+n=n*(n+1)/2

解决方案五：

O(n^2)