нужна помощь, чтобы решить эту проблему с помощью алгоритма... Даны два набора A и B с m и n элементами, соответственно, из линейного порядка. Эти наборы не обязательно отсортированы. Также предположим, что m ≤ n. Покажите, как вычислить A∪B и A ∩ B за время O(nlogm).
Вычисление объединения и пересечения двух несортированных массивов за время O(nlogm)
Ответы (1)
Как сказал vivek_23, вы можете добиться большего успеха, используя хеш-таблицу с высокой вероятностью.
Однако для достижения O(n log m) и при условии, что ваши наборы хранятся в виде массивов, вы можете отсортировать A в O (m log m) раз, а затем выполните n двоичный поиск для каждого элемента B, чтобы увидеть, находится ли он также в < em>А. Каждый поиск занимает O(log m) времени, в общей сложности O(n log m) времени.
Таким образом, для A∪B вы можете скопировать A в новый набор C за время O(m). . Затем для каждого элемента B вы выполняете поиск (бинарный поиск) в A. Если его нет в A, вы добавляете его в C. Таким образом, вы потратили бы O(m + n log m) время для построения C и O(m log m)* для сортировки A. Поскольку m ‹ n, общее время равно O(n log m), как вам и нужно.
Для A ∩ B вы начнете с пустого множества D. Для каждого элемента B вы выполняете поиск в A. Если он есть, вы добавите его в D. Когда вы закончите, вы выполните n поиск по A, всего (n log m)< /эм>.
Если бы вы вставили все элементы списка A в хеш-таблицу, а не сортировали их, вы могли бы сделать все за время O(m + n) с высокой вероятностью.
person
rrufai
schedule
02.11.2018
+1, но повторно: вы можете добиться большего успеха, используя хеш-таблицу с высокой вероятностью: это работает, только если у вас есть соответствующая хеш-функция, которая работает с этим типом элемента. В вопросе это не указано.
- person ruakh; 04.11.2018
O(n * log m)с помощью HashMap. - person nice_dev schedule 02.11.2018