与认识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 
     } 
    } 
} 

但第二个作品是如何超越我，我只是不明白的“增强”的可能(i, j)值的矩形而言

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

想起来了。第一个循环比较每对 - 所以它比较（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 
     } 
    } 
}