Задача 3SUM пытается идентифицировать 3 целых числа из набора размера такого что .
Предполагается, что не существует лучшего решения, чем квадратичное, то есть . Или, по-другому: .
Поэтому мне было интересно, применимо ли это к обобщенной задаче: найти целые числа для в наборе размером таком что .
Я думаю, что вы можете сделать это в для (обобщить простой алгоритм тривиально ).
Но есть ли лучшие алгоритмы для других значений ?
Ответы:
Для четного :k вычислить отсортированный список всех сумм входных элементов . Проверьте, содержит ли некоторое число и его отрицание . Алгоритм выполняется за времени.S k/2 S x −x O(nk/2logn)
Для нечетного :k Вычислить отсортированный список всех сумм входных элементов . Для каждого входного элемента проверьте, содержит ли и и , для некоторого числа . (Второй шаг - это, по сути, алгоритм времени для 3SUM.) Алгоритм выполняется за время .S (k−1)/2 a S x −a−x x O(n2) O(n(k+1)/2)
Оба алгоритма являются оптимальными (за исключением, возможно, логарифмического коэффициента, когда чётно и больше ) для любой константы в некотором слабом, но естественном ограничении модели вычисления линейного дерева решений. Для более подробной информации смотрите:k 2 k
Нир Айлон и Бернар Шазель. Нижние оценки для тестирования линейного вырождения . JACM 2005.
Джефф Эриксон Нижние оценки для линейных задач выполнимости . CJTCS 1999.
источник
Другими словами, предполагая экспоненциальную гипотезу времени , ваш алгоритм является оптимальным с точностью до постоянного множителя в экспоненте (множитель )n
(1) Михай Патраску и Райан Уильямс. О возможности более быстрых SAT-алгоритмов. Proc. 21-й симпозиум ACM / SIAM по дискретным алгоритмам (SODA2010)
источник
Вот несколько простых наблюдений.
Для вы можете сделать это за время , отсканировав массив на ноль. Для вы можете сделать это без хэширования во время . Сортируйте массив, а затем отсканируйте его. Для каждого элемента делаю бинарный поиск для . Это приводит к общей сложности . Для случая вы можете сделать это за время, накаплив массив и проверив результат.k=1 Θ(n) k=2 Θ(nlogn) i −i Θ(nlogn) k=n Θ(n)
Дополнительные сведения см. На странице «Проект открытых проблем» для 3SUM .
источник
См. Http://arxiv.org/abs/1407.4640
Новый алгоритм решения задачи rSUM Валерий Сопин
Аннотация:
Определен алгоритм для решения задачи rSUM для любого натурального r с субквадратичной оценкой сложности времени в некоторых случаях. С точки зрения количества используемой памяти полученный алгоритм имеет также субквадратичный порядок. Идея полученного алгоритма основана не на целых числах, а на k∈N последовательных битов этих чисел в двоичной системе счисления. Показано, что если сумма целых чисел равна нулю, то сумма чисел, представленных любыми k последовательными битами этих чисел, должна быть достаточно "близка" к нулю. Это позволяет отбросить числа, которые тем более не устанавливают решение.
Это что-то новое в этом выпуске.
источник