Хранение парных сумм в линейном пространстве

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

Я предполагаю, что мы не собираемся хранить все суммы, так как они n ^ 2 элемента не будут вписываться в n пространство и что мы просто распечатываем все в отсортированном порядке, так это значит, что мы должны динамически хранить предметы? Любые советы?

(это домашняя проблема)

Ответ 1

Проблема, насколько я понимаю, заключается в том, что мы хотим найти суммы

a1 + b1  a1 + b2  ...  a1 + bn
a2 + b1  a2 + b2  ...  a2 + bn
  ...      ...    ...    ...
an + b1  an + b2  ...  an + bn

и распечатайте их в отсортированном порядке. Ограничение заключается в использовании только O (n) памяти и O (n ^ 2 log n) времени в процессе.

Рассмотрим приведенную выше таблицу как n списки (строки) элементов n. Если мы отсортируем исходные массивы так, чтобы a1 <= a2 <= ... <= an и b1 <= b2 <= ... <= bn, каждый список уже отсортирован. Теперь проблема сводится к объединению отсортированных списков n.

Чтобы разработать это, подумайте о том, как объединить два отсортированных списка (как в MergeSort), затем три списка и т.д. Это тривиально распространяется на объединение n списков длины n в каждом из операций n для каждого выходного элемента, в общей сложности O (n^3). Теперь, что осталось, это сократить время для получения каждого выходного элемента до O (log n). Когда вы попросите намек, но не полное решение, посмотрите, можете ли вы сами справиться с этим шагом.

Ответ 2

В python вы можете что-то вроде этого:

import heapq

a = [2, 1, 3]
b = [4, 6, 5]

a.sort()
b.sort()

def add_to_b(x):
    for v in b:
        yield v + x

for v in heapq.merge(*[add_to_b(x) for x in a]):
    print v

Результат:

Идея состоит в том, что мы сортируем оба массива. Затем, добавляя к b, элемент из a определяет генератор возрастающих чисел. Поэтому мы создаем n такие генераторы, и мы объединяем их с помощью heapq.merge. Генератор, представленный функцией add выше, в определенное время требует постоянного пространства (пространство, необходимое для сохранения текущей позиции в b). heapq.merge сам нуждается в линейном пространстве. Поэтому нам нужно линейное пространство для выполнения алгоритма.

Ответ 3

Сначала соберите 2 массива в порядке возрастания, временная сложность 2 * O(n*lgn), которую можно также рассматривать как O(n*lgn). Затем используйте максимальную кучу с длиной n + 1 для поддержания минимальных n сумм.

Как поддерживать минимальные n сумм? Сначала наведите кучку a1 + b1, a1 + b2, a1 + b3,..., a1 + bn. Затем для каждого a[i], 1 <= i < n и b[j], 0 <= j < n нажмите a[i] + b[j], а затем нажмите самый большой из них:

for(int j=0;j<n;j++) {
    heap.push_into(a[0] + b[j]);
}
for(int i=1;i<n;i++) {
    for(int j=0;j<n;j++) {
        heap.push_into(a[i] + b[j]);
        heap.pop(); // remove the current largest sum in the heap, then the sums remain in the heap are the smallest n sums
    }
}

Тогда n элементов в куче - наименьшие n сумм.

Сложность времени O(n^2 * lgn), сложность пространства O(n).