Можем ли мы сделать алгоритм с 4 суммами в O (n ^ 2)?

Question

это связано со следующим вопросом:

https://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem

Без потери общности давайте рассмотрим только k или просто k = 4.

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

Если мы используем хэш-карту для хранения сумм в качестве ключа и ихсоответствующие индексные пары в качестве значения, тогда все операции могут выполняться за O(n^2) время.

Я что-то упустил в этом посте или это правда, что даже k, k -сумма может выполняться в O(n^{k/2}) время?

Спасибо!

Answer 1

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

Первый хеш-файл находится слева, и он будет храниться как значение (i1, j1), где i1 < j1 и j1 - это минимальный индекс, для которого эта сумма может бытьдостигается.

Второй хэш-файл справа, и он будет храниться как значение (i2, j2), где i2 < j2 и i2 - максимальный индекс, для которого эта сумма может быть достигнута.

Теперь бегите по клавишам первой хэш-карты, ища противоположную в другой.Если они оба там и j1 < i2, значит, у вас есть четверка.

Однако обратите внимание на тонкость.При сортировке ожидаемое и наихудшее время составляет O(n^2 log(n)).С хэшем ваше ожидаемое время составляет O(n^2), но теоретически возможно получить O(n^4), если ваш алгоритм хеширования выйдет из строя.(Алгоритмы хеширования обычно не ломаются на практике, поэтому мы считаем их O(1).)