Ответ 1
Если алгоритм должен был бы перечислить решения (т.е. наборы a, b, c и d, которые удовлетворяют условию), худшая временная сложность O (n 4):
1. Могут быть решения O (n 4)
Тривиальный пример - массив с только 0 значениями в нем. Затем a, b, c и d имеют всю свободу, пока они остаются в порядке. Это представляет собой решения O (n 4).
Но более общие массивы, которые следуют следующему шаблону, имеют решения O (n 4):
w, w, w, ... x, x, x, ..., y, y, y, ... z, z, z, ....
С таким же количеством вхождений каждого, и:
w + x + y = z
Однако, чтобы производить только количество решений, алгоритм может иметь лучшую временную сложность.
2. Алгоритм
Это небольшое изменение уже опубликованного алгоритма, который не включает фактор H. В нем также описывается, как обрабатывать случаи, когда разные конфигурации приводят к одинаковым суммам.
-
Извлеките все пары и сохраните их в массиве X, где каждый элемент получает следующую информацию:
a: наименьший индекс двух b: другой индекс
сумма: значениеxs[a] + xs[b] -
В то же время сохраняйте для каждой такой пары в другом массиве Y следующее:
c: наименьший индекс двух d: другой индекс
сумма: значениеxs[d] - xs[c]
Вышеуказанная операция имеет временную сложность O (n²)
- Сортируйте оба массива по их элементу сумма. В случае равных значений sum порядок сортировки будет определяться следующим образом: для массива X, увеличивая b; для массива Y, уменьшая c. Сортировку можно выполнить в
O (n²)O (n²logn).
[ Изменить: Я не мог доказать предыдущее утверждение O (n²) (если не сделаны некоторые предположения, которые позволяют использовать алгоритм сортировки по методу radix/bucket, который я не предполагается). Как отмечено в комментариях, в общем случае массив с элементами n² может быть отсортирован в O (n²logn²), который O (n²logn), но не O (n²)]
-
Пройдите оба массива в "тандем", чтобы найти пары сумм, которые равны. Если это так, необходимо проверить, что
X[i].b < Y[j].c. Если это так, то это решение. Но их могло быть много, и подсчет тех, кто в приемлемое время, нуждается в особой заботе.Пусть
m = n(n-1)/2, то есть количество элементов в массиве X (что также является размером массива Y):
i = 0
j = 0
while i < m and j < m:
if X[i].sum < Y[j].sum:
i = i + 1
elif X[i].sum > Y[j].sum:
j = j + 1
else:
# We have a solution. Need to count all others that have same sums in X and Y.
# Find last match in Y and set k as index to it:
countY = 0
while k < m and X[i].sum == Y[j].sum and X[i].b < Y[j].c:
countY = countY + 1
j = j + 1
k = j - 1
# add chunks to `count`:
while i < m and countY >= 0 and X[i].sum == Y[k].sum:
while countY >= 0 and X[i].b >= Y[k].c:
countY = countY - 1
k = k - 1
count = count + countY
i = i + 1
Обратите внимание, что хотя есть вложенные циклы, переменная i только увеличивается, а значит j. Переменная k всегда уменьшается в самом внутреннем цикле. Хотя он также получает более высокие значения для начала, он никогда не сможет адресовать один и тот же элемент Y больше, чем постоянное число раз, через индекс k, поскольку, уменьшая этот показатель, он остается в пределах "той же суммы" Y.
Итак, это означает, что эта последняя часть алгоритма работает в O (m), которая O (n²). Поскольку мое последнее редактирование подтвердило, что шаг сортировки не O (n²), этот шаг определяет общую временную сложность: O (n²logn).