6SUM: При заданном наборе S из n целых чисел существует ли подмножество S с ровно 6 элементами, сумма которых равна 0?Как сделать лучше, чем O (n ^ 3)?

Question

Я подумал об этом простом алгоритме для решения задачи 6SUM, который использует O (n ^ 3) времени и пространства: сгенерируйте все наборы троек и поместите их в хеш-таблицу, где ключ - это сумма троек.Затем выполните итерации ключей хеш-таблицы: для каждого ключа k1 посмотрите, существует ли другой ключ k2, такой что k2 = S-k1

Какой алгоритм эффективнее?Это не домашняя проблема.

Answer 1

Ваш алгоритм - Омега (n ^ 6) в худшем случае, это всего O (n ^ 3) в среднем случае.Вы игнорируете возможность коллизий хеш-таблиц.Вы можете сделать это O (n ^ 3 logn), используя взамен сбалансированное дерево.

Кроме того, это в P, так как существует тривиальный алгоритм полиномиального времени для проверки каждой возможной комбинации из 6 чисел,поэтому упоминание рюкзака и т. д. не имеет значения.

Как и в случае задачи 3-SUM, я считаю, что задача r-sum имеет алгоритм o (n ^ [r / 2]), (примечание: smallOH и [x] = наибольшее целое число> = x, например, [5/2] = 3) все еще открыто.

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

Таким образом, достижение лучшего, чем O (n ^ 3) (то есть o (n ^ 3)) может быть открытой проблемой.