與認識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 
     } 
    } 
}