2 tidusnake tidusnake 于 2016.03.24 10:27 提问

一个关于时间复杂度问题
 for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
    // do something
    }
}

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

5个回答

qq423399099
qq423399099   Ds   Rxr 2016.03.24 10:38
已采纳

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

sl_18500
sl_18500   2016.03.24 10:35

当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

fickyou
fickyou   2016.03.24 10:39

对,就是O(n^2)

huixion
huixion   2016.03.24 10:39

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

enpterexpress
enpterexpress   2016.03.24 10:57

O(n^2)

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!