Поиск подмножества из четырех элементов, которые добавляются к целевой сумме S, может быть выполнен за время O (n ^ 2) путем хэширования всех попарных сумм x, а также хеширования S - x до тех пор, пока не будет найдено нетривиальное столкновение. Однако у хеширования есть проблемы; можно ли исправить это, чтобы добиться гарантированного времени O(n^2) для поиска подмножества из 4 элементов, которое добавляется к целевой сумме S без хеширования, и, что более важно, известно, можно ли добиться большего, чем O(n ^2) время?
Нижняя граница и удаление хеширования для поиска подмножества размера 4, которое добавляется к целевой сумме
comment
возможный дубликат найти четыре элемента в массиве, сумма которого равна заданному числу X
- person Bernhard Barker schedule 13.04.2014
comment
3SUM — более простая задача, и ее нельзя решить менее чем за O(n²) времени ( насколько нам известно), так что предположительно и этого быть не может.
- person Bernhard Barker schedule 13.04.2014
comment
@Dukeling Я вижу, что это частичный дубликат, потому что было найдено время O (n ^ 2), но сложность в наихудшем случае - это другой вопрос. Может быть, можно доказать, что 4SUM является омегой (n ^ 2) или чем-то близким, даже если это невозможно доказать для 3SUM.
- person user2566092 schedule 13.04.2014
comment
Если целевые числа являются целыми числами в диапазоне размера C (например, A ‹= x_i ‹= A + C), то можно вычислить попарные суммы в O (C log C) с помощью БПФ.
- person Niklas B. schedule 13.04.2014
comment
Если связанный пост отвечает на остальную часть вашего вопроса, я предлагаю вам отредактировать свой вопрос, чтобы сосредоточиться на оставшейся части (но вам может повезти больше на Computer Science с этим). Хотя разве недостаточно того, что никто не смог придумать алгоритм быстрее, чем O(n²), для предположительно более простой задачи? Вам действительно нужно явное доказательство?
- person Bernhard Barker schedule 14.04.2014
comment
Интересный вопрос здесь заключается в том, можем ли мы сбрить журнал (n ^ 2 log n -> n ^ 2) без чего-то с плохим худшим случаем (например, хеширование). К сожалению, мы не знаем, как отсортировать S + S за время O(n^2).
- person David Eisenstat schedule 14.04.2014
