Блог

Главная - Вопросы по программированию - проблема разделения и императива

проблема разделения и императива

#algorithm #language-agnostic #divide-and-conquer

#алгоритм #язык не зависит #разделяй и властвуй

Вопрос:

Учитывая множество M, найдите, существует ли пара чисел (a, b), оба из которых принадлежат M, и a b = x, где x — ранее указанный параметр. Проблема должна быть решена с использованием «Разделяй и властвуй» в O (n * log n). Вероятно, проблему следует разделить на две подзадачи половинного размера, а затем рекомбинировать результаты в O (n).

Я хотел бы получить псевдокод для данной проблемы или подсказку для ее решения.

Комментарии:

1. Могут ли быть отрицательные значения в M ?

2. Я доволен решением для любой версии проблемы.

3. вы можете достичь O (n), используя хэш

4. @Amit: Это вопрос домашнего задания о сложности наихудшего случая, не имеет значения, что хэш-функция должна «стараться изо всех сил», важно, что это наихудший случай O (n ^ 2), когда вопрос требует наихудшего случая O (n lg n). Также в вопросе явно предлагается подход «разделяй и властвуй».

5. Если хэш-функция определена следующим образом f:M-> HashDomain, вы можете легко создать входной набор M с card(M)>card(HashDomain), и это сделает хэш-функцию не инъективной => будут появляться коллизии => не O (n).

Ответ №1:

Не уверен, соответствует ли это вашим требованиям, но:

  1. Сортировка множества слиянием (здесь используется метод «разделяй и властвуй»).
  2. Начните с первого и последнего элементов набора и сравните их сумму с x. Если сумма равна, вы закончили. Если сумма больше, перейдите к предпоследнему элементу, если сумма меньше, перейдите ко второму элементу.
  3. Повторяйте второй шаг, двигаясь от концов к центру отсортированного набора, пока не будут найдены элементы, суммирующие значение x, или пока элементов больше не останется.

Сортировка «разделяй и властвуй» равна O (n lg n), пошаговое прохождение по отсортированному набору равно O (n), следовательно, общая сложность равна O (n lg n).

Ed: сумма равна x, а не M.

Ответ №2:

Если вы отсортируете M (в O (n log n), используя D amp; I), вы можете проверить за линейное время, есть ли пара с правильной суммой. (Подсказка: два указателя).

Если вы не думаете, что это будет считаться решением D amp; I, вы можете включить этап проверки в этап объединения сортировки и завершить работу раньше, если найдете совпадение.

Дополнение: Если вы выполняете проверку во время объединения, вы в конечном итоге выполняете O (n log n) шагов добавления и сравнения вместо O (n) — но, конечно, это не ухудшает асимптотическое время выполнения, за исключением постоянного коэффициента.