java - 坚持理解2个for循环

Question

我正在使用此网站作为资源 http://www.perlmonks.org/?node_id=573138

我试图理解 O 表示法，它给出了两个在两个数组中搜索同一元素的示例。第一个示例与第二个示例一样具有 O(n^2) ，但是第二个示例对其进行了增强，因此它运行得更快，但仍然保持相同的 O 表示法，我将粘贴下面的代码示例。我想知道的是它们是如何工作的，我的编程知识有限，并且对java最熟悉，我可以理解我认为的第一个，只是两个for循环和检查，类似；

for (int i = 0; i < arrarysize ; i++){
    for (int j = 0; j < arraysize; j++){
        if(getElementFromArray(i).equals(getElementFromArray(j))){
            //do something
        }
    }
}

但是第二个如何工作超出了我的范围，我只是没有得到“增强”

for my $i (0 .. $#array) {
    for my $j (0 .. $#array) {
        next if $j == $i;
        # Compare $i, $j
    }
}

for my $i (0 .. $#array - 1) {
    for my $j ($i + 1 .. $#array) {
        # Compare $i, $j
    }
}

Answer 1

将其视为可能的 (i, j) 值的矩形。第一个循环比较每对 - 因此它比较 (5, 0)，然后比较 (0, 5)，这显然只会给出相反的结果。

第二个循环将该矩形一分为二 - 基本上它只检查它的一个“三角形” - 每个值 j > i 所以它会检查 (0, 5) 而不是 (5, 0)。这避免了冗余 - 但这只是意味着它正在检查 n*(n-1)/2 值而不是 n^2 值 - 它仍然是 O(n ^2).

Java 中的第二个循环是:

for (int i = 0; i < arraysize - 1; i++) {
    for (int j = i + 1; j < arraysize; j++){
        if(i == j) {
            //do something
        }
    }
}