Слияние двух отсортированных массивов с O (log (n + m)) Худший случай

Question

Какой алгоритм я могу использовать для объединения двух отсортированных массивов в один отсортированный массив с наихудшей временной сложностью O (log (m + n)) где n, m - длина массивов? У меня очень мало опыта работы с алгоритмами, но я проверил сортировку слиянием и, похоже, сложность времени для этапа слияния равна O (n). Существует ли другой подход к объединению в O (log (n))?

Редактировать: Я не рассматривал первоначально, но, возможно, невозможно объединить два отсортированных массива в O (log (n))? Фактическая цель - найти медиану двух отсортированных массивов. Есть ли способ сделать это без их слияния?

Единственная идея, которая у меня была, я прочитал, что слияние двух биномиальных кучек - это O (log (n)), но превращение массива в биномиальную кучу - это O (n). Я думаю, что это не сработает.

Edit2: Я собираюсь опубликовать новый вопрос, потому что понял, что слияние никогда не будет работать достаточно быстро. Я думаю, вместо этого мне нужно выполнить бинарный поиск по каждому массиву, чтобы найти медиану в log (n).

Answer 1

Я не думаю, что существует алгоритм, который бы объединить два массива в O(log(n+m)) времени.

И это имеет смысл, когда вы об этом думаете. Если вы пытаетесь создать новый отсортированный массив из n+m элементов, вам нужно будет сделать не менее n+m копий. Нет никакого способа обойти это.

Я думаю, что лучшим способом было бы перебирать каждый массив одновременно и на каждой итерации сравнивать значения обоих элементов. Если один меньше другого (если вы хотите, чтобы массив отсортировался в порядке убывания), скопируйте этот элемент в массив и увеличьте указатель указателя для этого массива и наоборот. Если оба элемента одинаковы, вы можете просто добавить их в новый отсортированный массив и увеличить оба указателя.

Продолжайте, пока один из указателей не достигнет конца своего соответствующего массива, а затем скопируйте оставшуюся часть другого массива один раз.

Это должно быть O(m+n)

Что касается вашего редактирования, есть способ, чтобы найти медиану двух отдельных массивов в log(n + m) времени.

Вы можете сначала найти медиану двух отсортированных массивов (средний элемент) и сравнить их. Если они равны, то это медиана. Если медианная первая больше, чем вторая, вы знаете, что медиана должна находиться либо в первой половине первого массива, либо во второй половине второго массива, и наоборот, если медиана первого меньше, чем вторая.

Этот метод сокращает ваше пространство поиска в половину каждой итерации и, таким образом, log(n + m)

Answer 2

Вам необходимо объединить массивы. так что, несмотря ни на что, вам нужно по крайней мере пересечь 2 массива, поэтому сложность не может быть меньше o (m + n)

Answer 3

Возможно, вы думаете о The Selection Algorithm.

Для сортированной структуры данных поиск медианного значения равен O (1). Для несортированной структуры данных (или структуры данных, в которой данные сортируются по двум логическим разделам) среда выполнения O (n).

Возможно, вы могли бы осуществить его с помощью алгоритма с параллельным сокращением, но я думаю, что это обман в терминах Runtime Analysis.

Так что я не верю, что есть алгоритм, который уменьшает его ниже O (N) (или, в вашем случае, O (N + M))