застрял с пониманием 2 для петель

Question

я использую этот сайт как ресурс http://www.perlmonks.org/?node_id=573138

Я пытаюсь понять нотацию O, и она приводит два примера поиска в двух массивах одного и того же элемента. Первый пример имеет O (n ^ 2), как и второй, однако второй имеет усовершенствование, поэтому он работает быстрее, но все еще поддерживает ту же запись O, я вставлю примеры кода ниже. Что я хотел бы знать, так это то, как они работают, у меня ограниченные знания в области программирования и я чувствую себя наиболее комфортно в Java, я могу понять первое, что я думаю, только два для циклов и проверки, что-то вроде;

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
        }
    }
}