Вопрос по complexity-theory – Временная сложность объединения двух отсортированных массивов размером n и m

5

Мне просто интересно, какова временная сложность объединения двух отсортированных массивов размера n и m, учитывая, чтоn is always greater than m.

Я думал об использовании сортировки слиянием, которая, как я полагаю, в этом случае будет использовать O (log n + m).

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

Заранее спасибо.

Должно быть летнее время, но домашнее задание? Windle

Ваш Ответ

2   ответа
27

(m log n). Это O (n + m).

Код выглядит примерно так:

allocate c with length n+m
i = 1
j = 1
while i < n or j < m
  if i = n
    copy rest of b into c 
    break    
  if j = m
    copy rest of a into c
    break
  if a[i] < b[j]
    copy a[i] into c
    i=i+1
    continue
  if b[j] < a[i]
    copy b[j] into c
    j=j+1
    continue

Теперь, если у нас недостаточно памяти для выделения c, это можно изменить, чтобы оно по-прежнему составляло O (n + m) времени, поскольку большинство аппаратных средств (например, RAM и жесткие диски) допускают операции с блоками. когда нам нужно вставить один элемент в середину массива, это - одна операция, чтобы переместить хвостовую часть блока по одному, чтобы освободить место. Если бы вы работали на оборудовании, которое не позволяло этого, то, возможно, у вас было бы O (n) для каждой вставки, что тогда было бы сложностью O (n + mn). Поскольку нам нужно только вставить элементы меньшего массива в больший, нам никогда не нужно сдвигать части большего массива, когда элемент из этого уже находится в нужном месте. Следовательно, n остается неизменным, и сложность m-бита увеличивается. Это наихудший случай, когда весь массив b длиной m правильно расположен перед массивом a длины n.

В зависимости от того, находится ли m в тэте (n) или нет, делает O (n + m) медленнее, чем O (m log n). Я не проверял ваш алгоритм, но это определенно можно сделать за O (n), см. Мой комментарий к ответу Дмитрия.
предположим, что они являются уникальным номером
Не должны ли мы рассмотреть случай: a [i] = b [j]?
-10

Attention! This answer contains an error

Существует более эффективный алгоритм, и он представлен в другом ответе.

Сложность O (m log n).

Пусть длинный массив будет вызванa и короткий массив будетb тогда описанный вами алгоритм можно записать в виде

  for each x in b
      insert x into a

Есть итерации цикла. Каждая вставка в отсортированный массив является операцией O (log n). Следовательно, общая сложность составляет O (m log n).

посколькуb отсортированный выше алгоритм можно сделать более эффективным

  for q from 1 to m
      if q == 1 then insert b[q] into a
      else 
         insert b[q] into a starting from the position of b[q-1]

Может ли это дать лучшую асимптотическую сложность? На самом деле, нет.

Предположим, элементы изb равномерно распределены вдольa, Тогда каждая вставка займетO(log (n/m)) и общая сложность будетO(m log(n/m) ), Если существует постояннаяk>1 это не зависит отn или жеm такой, чтоn > k * m затемO(log(n/m)) = O(log(n)) и мы получаем ту же асимптотическую сложность, что и выше.

"Следовательно, общая сложность составляет O (m log n)". Вставка в массив из n элементов сама по себе является операцией O (n), потому что каждый элемент должен быть смещен вправо. Таким образом, O (m * log n) в приведенном выше предложении на самом деле будет O (mn войти n)?
Между прочим, извините за отрицательный голос - я первоначально думал, что ваш ответ просто неэффективен, но пришел к выводу, что это не так. ТАК не дадим мне снова поднять голос, если только ответ не отредактирован; может ты сможешь это сделать?
Операция может быть выполнена в O (m + n) = O (n), так как m & lt; n. Используйте массивы как очереди, сохраняя указатель на следующий элемент, который будет использоваться в каждом массиве, сравнивайте оба значения, прежде чем вставлять их в новый массив. Есть ровно n + m сравнений, время выполнения равно O (n). В зависимости от того, насколько различны m и n (например, если m в тета (n)), ваше решение может быть логарифмически медленнее, чем это. Это также может быть экспоненциально быстрее, если, например, m находится в O (1).

Похожие вопросы