Обобщенная проблема 3SUM (k-SUM)?

29

Задача 3SUM пытается идентифицировать 3 целых числа из набора размера такого что .a,b,cSna+b+c=0

Предполагается, что не существует лучшего решения, чем квадратичное, то есть . Или, по-другому: .o(n2)o(nlog(n)+n2)

Поэтому мне было интересно, применимо ли это к обобщенной задаче: найти целые числа для в наборе размером таком что .aii[1..k]Sni[1..k]ai=0

Я думаю, что вы можете сделать это в для (обобщить простой алгоритм тривиально ). Но есть ли лучшие алгоритмы для других значений ?o(nlog(n)+nk1)k2k=3
k

битовая
источник
последние новости / статья о 3SUM, в которой рассматриваются нижние границы сложности дерева решений
vzn

Ответы:

27

k SUM может быть решена быстрее следующим образом.

  • Для четного :k вычислить отсортированный список всех сумм входных элементов . Проверьте, содержит ли некоторое число и его отрицание . Алгоритм выполняется за времени.Sk/2SxxO(nk/2logn)

  • Для нечетного :k Вычислить отсортированный список всех сумм входных элементов . Для каждого входного элемента проверьте, содержит ли и и , для некоторого числа . (Второй шаг - это, по сути, алгоритм времени для 3SUM.) Алгоритм выполняется за время .S(k1)/2aSxaxxO(n2)O(n(k+1)/2)

Оба алгоритма являются оптимальными (за исключением, возможно, логарифмического коэффициента, когда чётно и больше ) для любой константы в некотором слабом, но естественном ограничении модели вычисления линейного дерева решений. Для более подробной информации смотрите:k2k

JeffE
источник
stackoverflow.com/a/14737071/511736 предлагают алгоритм O (n ^ 2), когда k = 4
Kowser
1
Хэширование - это обман. Алгоритм, описанный в StackOverflow, запускается только за O (n ^ 2) для целочисленного ввода, и только с высокой вероятностью и только в том случае, если вы используете подходящую случайную хэш-функцию. Алгоритмы в моем ответе работают в реальной модели ОЗУ, они полностью детерминированы, а временные границы - наихудший случай. Вы также можете сбрить лог-факторы в целочисленных настройках, используя «хитрости», но это довольно скучно.
Джефф
12

d -SUM требует времени если k-SAT не может быть решена за времени для любой константы k. Это было показано в статье Михая Патраску и Райана Уильямса (1).nΩ(d)2o(n)

Другими словами, предполагая экспоненциальную гипотезу времени , ваш алгоритм является оптимальным с точностью до постоянного множителя в экспоненте (множитель )n

(1) Михай Патраску и Райан Уильямс. О возможности более быстрых SAT-алгоритмов. Proc. 21-й симпозиум ACM / SIAM по дискретным алгоритмам (SODA2010)

Samm
источник
3

Вот несколько простых наблюдений.

Для вы можете сделать это за время , отсканировав массив на ноль. Для вы можете сделать это без хэширования во время . Сортируйте массив, а затем отсканируйте его. Для каждого элемента делаю бинарный поиск для . Это приводит к общей сложности . Для случая вы можете сделать это за время, накаплив массив и проверив результат.k=1Θ(n)k=2Θ(nlogn)iiΘ(nlogn)k=nΘ(n)

Дополнительные сведения см. На странице «Проект открытых проблем» для 3SUM .

Юхо
источник
-1

См. Http://arxiv.org/abs/1407.4640

Новый алгоритм решения задачи rSUM Валерий Сопин

Аннотация:

Определен алгоритм для решения задачи rSUM для любого натурального r с субквадратичной оценкой сложности времени в некоторых случаях. С точки зрения количества используемой памяти полученный алгоритм имеет также субквадратичный порядок. Идея полученного алгоритма основана не на целых числах, а на k∈N последовательных битов этих чисел в двоичной системе счисления. Показано, что если сумма целых чисел равна нулю, то сумма чисел, представленных любыми k последовательными битами этих чисел, должна быть достаточно "близка" к нулю. Это позволяет отбросить числа, которые тем более не устанавливают решение.

Это что-то новое в этом выпуске.

user20970
источник
1
Не могли бы вы явно привести результаты статьи, которые имеют отношение к вопросу? (Вставить тезисы можно, если статья в целом актуальна.) Предполагается, что посты на SE должны быть не просто ссылкой.
FrankW
1
Как таковой, этот ответ является (потенциально полезным) комментарием, а не ответом. Как таковой, он должен содержать некоторый оригинальный контент, например, ваше описание алгоритма своими словами. Вы хотите это сделать? Я могу преобразовать ваш ответ в комментарий, если вы этого не сделаете. (Я знаю, что вы не могли комментировать из-за вашего представителя.)
Рафаэль
Это не похоже на заслуживающую доверия бумагу. Утверждение «субквадратичная сложность по времени в некоторых случаях» не является полезным утверждением. Временная сложность по определению является наихудшим временем выполнения. В некоторых случаях пузырьковая сортировка выполняется за линейное время, но ее временная сложность остается квадратичной.
DW