coincé avec compréhension pour les boucles 2

Question

J'utilise ce site comme une ressource http://www.perlmonks.org/?node_id=573138

Je suis en train de comprendre au sujet de la notation O et donne deux exemples de recherche deux tableaux pour le même élément. Le premier exemple a O (n^2) comme le second, cependant le second a une amélioration pour qu'il s'exécute plus vite mais conserve la même notation O, je vais coller les exemples de code ci-dessous. Ce que je voudrais savoir, c'est comment ils fonctionnent, j'ai des connaissances limitées en programmation et je suis le plus à l'aise en Java, je peux comprendre le premier je pense, juste deux pour les boucles et vérifier, quelque chose comme;

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

mais comment la deuxième œuvres est au-delà de moi, je ne comprends pas le « amélioration »

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

penser en termes d'un rectangle de (i, j) valeurs possibles. La première boucle compare chaque paire - ainsi elle compare (5, 0) et compare plus tard (0, 5) ce qui évidemment donnera juste le résultat opposé. La seconde boucle divise ce rectangle en deux moitiés - fondamentalement, il ne vérifie qu'un "triangle" - toutes les valeurs où j > i donc il vérifie (0, 5) mais pas (5, 0). Cela évite la redondance - mais cela signifie simplement qu'il vérifie n*(n-1)/2 valeurs au lieu de n^2 valeurs - il est toujours O(n^2).

La seconde boucle en Java serait:

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