java - 二重にネストされた for ループの複雑さの違いは? (ジャワ)

Question

これら 2 つのネストされた 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

最初のループは 2 番目のループの約 2 倍の速さですが、漸近的な時間の複雑さに関しては同じです。

O(N^2)

グラフィカルに考えることができます: 各辺に N 単位の正方形を想像してください。2 番目のループは、すべての単位正方形にアクセスします。

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

最初のループは、正方形の半分を覆う三角形に属する点を訪れます。

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

Answer 2

両方のループの漸近動作は同じです - O(n**2)

1. 1 回目のループ:1 + 2 + ... + n = n(n+1)/2 = n*n/2 + n/2 -> O(n**2)
2. 2 番目のループ:n*n -> O(n**2)

したがって、2 番目のループは 1 番目のループのほぼ 2 倍遅くなりますが、漸近法は同じです。