Можно ли разбить последовательность чисел на две группы на основе среднего значения без сортировки?

Question

Существует ли алгоритм разделения последовательности случайных чисел на две группы на основе медианного значения, определенного на лету (без их сортировки)?

Пример.Если бы у меня была последовательность 2-3-6-7-1-4-5, результатом были бы две отдельные группы:

A) 1 2 3

B) 5 6 7

Медиана: 4

Answer 1

Вы можете найти медиану массива (и разделить) в линейное время .

Answer 2

Алгоритм BFPRT (Blum-Floyd-Pratt-Rivest-Tarjan) (см. wiki ) может найти медиану в линейном времени, то есть в O(n).

Однако постоянная «скрытая» в примечании O настолько велика, что на практике быстрее отсортировать массив в O(n log n) для разумных размеров массива.

Answer 3

Да, это можно сделать в O (n) .

Прежде всего, если бы мы уже знали медиану, мы могли бы легко разделить последовательность на два в O (n) путем итерации последовательности и сравнения каждого значения с медианой.Итак, как нам найти медиану в O (n) ?

Основная идея состоит в том, чтобы использовать быструю сортировку , но вместо рекурсивной сортировки обеих сторон оси, сортирует только половину, содержащую медиану (т.е. половину, которая включает в себя индекс ⌈n/2⌉).Если наш выбор оси гарантирует геометрическую сходимость быстрой сортировки (как медиана медиан делает), то наш общий алгоритм будет O (n).

Алгоритм

Давайте назовем текущий размер нашего массива k , а сокращение из-за медианы медиан c - т.е.наша точка отсчета гарантирует сжатие массива не менее чем на c каждый шаг

1. Оцените медиану массива, используя медиану медиан - O(k)
2. Разделение массива в стиле быстрой сортировки (с оценкой в ​​качестве нашей оси) - O (k)
3. Выберите половину массива, содержащуюМедиана (индекс ⌈n/2⌉).Этот новый подмассив будет иметь размер не более k/c.Повторяйте шаги 1 и 2 до тех пор, пока мы не определим элемент, позиция которого в исходном массиве равна ⌈n/2⌉.

Асимптотическое время выполнения этого алгоритма равно

2 O (n) + 2 O (н / с) + 2 O (н / с ² ) + 2 O (н / с ³ ) + ...
= O (n)

Answer 4

Вы можете найти медиану, найдя среднее между вторым (n / 2) -ым самым большим элементом и минимальным (n / 2) -ым элементом.Это можно сделать с помощью этого предыдущего вопроса SO .

После этого просто выполните итерацию по вашему массиву, поместив элементы, большие, чем медиана, в один и ниже, чем медиана, в другой.

---

В качестве альтернативы, если вы знали размер вашей последовательности, вы могли бы создать две коллекции размера пола (n / 2): одну «наименьшую половину» ( S ) и одну«наибольшая половина» ( L ), а затем один за другим:

• Выньте один элемент из вашей последовательности, назовите его e .
• Поместите его в S , если S не заполнен.
• Если S заполнен, найдите самый большой элемент ( S | e ) (объединение двух) (это может быть реализовано путем итерации по S , пока элемент не станет больше e найден, если ничего не найдено, это e , иначе это найденный элемент) и добавьте его к L .Если это наибольшее значение было в S , введите e в S для его повторного заполнения.
• Если L полное, найдите наименьший элемент ( L | e ) и удалите его, добавив e в L , если e не было удалено.

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

ruby-реализация (с большим количеством ярлыков неработоспособности):

def split_into_halves to_split
  s = []
  l = []
  medianlimit = to_split.size/2
  for e in to_split
    if s.size < medianlimit
      s.push(e)
    else

      if s.max >= n
        max = s.max
        s.delete max
        s.push(e)
      else
        max = e
      end

      if l.size < medianlimit
        l.push(max)
      elsif l.max >= max
        l.delete l.max
        l.push(max)
      end

    end
  end

  return [s,l]
end

k = [2,3,6,7,1,4,5]
split_into_halves(k) #=> [[2,3,1],[6,4,5]]