java - 双嵌套for循环之间的复杂性差异？ ( java )

Question

这两个嵌套 for 循环在性能和复杂性方面有何不同？

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

和:

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

Answer 1

第一个循环的速度大约是第二个循环的两倍，但就渐近时间复杂度而言，它们是相同的:

O(N^2)

你可以用图形来思考它:想象一个正方形，每边有 N 个单位。第二个循环访问所有单位方 block ；

######
######
######
######
######
######

第一个循环访问属于覆盖一半正方形的三角形的点:

#
##
###
####
#####
######