проблема «разделяй и властвуй»

Question

Для заданного набора M найдите, существует ли пара чисел (a, b), оба из которых принадлежат M, и a + b = x, где x - ранее указанный параметр. Проблема должна быть решена с помощью Divide et Impera в O (n * log n). Вероятно, проблема должна быть разбита на две подзадачи половинного размера, а затем рекомбинировать результаты в O (n).

Мне нужен псевдокод для данной проблемы или подсказка для ее решения.

Answer 1

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

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

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

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

Answer 2

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

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

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