Почему решение проблемы двух сумм с использованием 2 вложенных циклов, сложность O(n^2), выполняется намного быстрее при изменении только логики счетчика циклов?

Question

Решение проблемы двух сумм может быть реализовано с использованием алгоритма сложности O(n), но я только что опробовал сложность O(n^2), которая является наивным подходом с использованием 2 вложенных циклов, которые проверяют сумму каждого i-го целого числа с каждым из остальные целые числа по отношению к целевому значению, далее - реализация O(n^2), для двух реализаций, nums - это массив целых чисел, n - размер nums, а index - это массив размера 2 для хранения индексов из 2 целых чисел

for(int i=0; i<n; ++i)
for(int j=i+1; j<n; ++j) {
    if(nums[i] + nums[j] == target) {
        indices[0] = i; indices[1] = j; return indices;
    }
}

Эта реализация решает проблему за 140 мс. Я попробовал другой подход O(n^2), который для каждого значения k, начиная с 1 до n-1, проверяет сумму i-го целого числа и (i+k) -го целого числа на целевое значение, ниже приводится реализация,

for(int k=1; k<n; k++)
for(i=0; i<n-k; i++) {
    int j=i+k;
    if(nums[i] + nums[j] == target) {
        indices[0] = i; indices[1] = j; return indices;
    }
}

как видите, то же тело цикла, но оно выполняется намного быстрее, время выполнения 8 мс. Это почему? Связано ли это с пространственной локальностью?

Answer 1

При честном сравнении обе программы выполнялись бы до конца и по-прежнему НЕ находили индексы. Судя по всему, вы проверяете случай, в котором есть ответ. Естественно, в этом случае порядок, в котором мы ищем ответ, имеет большое значение.

Например, когда единственный ответ - {n - 2, n - 1}, первый код потребует O(n^2) операций, чтобы найти его, а второй находит его за O(n). Код для генерации:

std::fill (&num[0], &num[0] + n, 0);
target = 2;
num[n - 2] = 1;
num[n - 1] = 1;

И наоборот, когда единственный ответ - {0, n - 1}, первый код находит его за O(n), а второй займет O(n^2) шагов. Код для генерации:

std::fill (&num[0], &num[0] + n, 0);
target = 2;
num[0] = 1;
num[n - 1] = 1;

В &num[0] главное убедиться, что он работает, num это массив или вектор.