Почему время выполнения сортировки слиянием в наихудшем случае O (n log n)?

Question

Может ли кто-нибудь объяснить мне простым английским языком или простым способом объяснить это?

Answer 1

Сортировка слиянием использует подход Разделяй и властвуй для решения проблемы сортировки. Во-первых, он делит входные данные пополам, используя рекурсию. После разделения он сортирует половинки и объединяет их в один отсортированный вывод. Смотрите рисунок

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

Псевдокод для сортировки слиянием действительно прост.

# C = output [length = N]
# A 1st sorted half [N/2]
# B 2nd sorted half [N/2]
i = j = 1
for k = 1 to n
    if A[i] < B[j]
        C[k] = A[i]
        i++
    else
        C[k] = B[j]
        j++

Легко видеть, что в каждом цикле у вас будет 4 операции: k ++ , i ++ или j ++ , оператор if и атрибуция C = A | B . Таким образом, у вас будет меньше или равно 4N + 2 операций, что создает сложность O (N) . Для доказательства 4N + 2 будет рассматриваться как 6N, поскольку верно для N = 1 ( 4N +2 <= 6N </strong>).

Итак, предположим, что у вас есть вход с N элементами и предположим, что N - это степень 2. На каждом уровне у вас в два раза больше подзадач с входом с половиной элементов из предыдущий ввод. Это означает, что на уровне j = 0, 1, 2, ..., lgN будут присутствовать 2 ^ j подзадач с входом длины N / 2 ^ J . Количество операций на каждом уровне j будет меньше или равно

2 ^ j * 6 (N / 2 ^ j) = 6N

Обратите внимание, что не имеет значения, какой уровень у вас всегда будет меньше или равен 6N операций.

Поскольку существует lgN + 1 уровней, сложность будет

O (6N * (lgN + 1)) = O (6N * lgN + 6N) = O (n lgN) * ​​1057 *

Ссылки:

• Coursera Алгоритмы курса: разработка и анализ, часть 1

Answer 2

В «традиционной» сортировке слиянием каждый проход данных удваивает размер отсортированных подразделов. После первого прохода файл будет отсортирован по разделам длиной два. После второго прохода длина четыре. Затем восемь, шестнадцать и т. Д. До размера файла.

Необходимо продолжать удваивать размер отсортированных разделов, пока не будет один раздел, содержащий весь файл. Для достижения размера файла потребуется lg (N) удвоений размера раздела, и каждый проход данных займет время, пропорциональное количеству записей.

Answer 3

Это потому, что в худшем или среднем случае сортировка слиянием просто делит массив на две половины на каждом этапе, что дает ему компонент lg (n), а другой N-компонент получается из его сравнений, выполненных на каждом этапе , Таким образом, объединение становится почти O (nlg n). Независимо от того, является ли средний случай или худший случай, фактор lg (n) всегда присутствует. Коэффициент N покоя зависит от сделанных сравнений, которые исходят из сравнений, выполненных в обоих случаях. Теперь наихудший случай - это случай, когда N-сравнение происходит для N-входа на каждом этапе. Таким образом, он становится O (nlg n).

Answer 4

После разбиения массива на стадию, где у вас есть отдельные элементы, то есть назовите их подсписками,

• на каждом этапе мы сравниваем элементы каждого подсписка со смежным подсписком.Например, [Повторное использование изображения @ Дэви]

  

  1. На этапе 1 каждый элемент сравнивается со смежным, поэтому n / 2сравнения.
  2. На Этапе-2 каждый элемент подсписка сравнивается со своим смежным подсписком, поскольку каждый подсписок отсортирован, это означает, что максимальное количество сравнений, сделанных между двумя подсписками, составляет <= длина подсписка, т.е.2 (на Этапе-2) и 4 сравнения на Этапе-3 и 8 на Этапе-4, так как сублилисты продолжают удваиваться по длине.Что означает максимальное количество сравнений на каждом этапе = (длина подсписка * (количество подсписков / 2)) ==> n / 2
  3. Как вы уже заметили, общее количество этапов будет log(n) base 2 Таким образом, общая сложность будет равна == (максимальное количество сравнений на каждом этапе * количество этапов) == O ((n / 2) * log (n)) ==> O (nlog (n))

Answer 5

Алгоритм сортировки слиянием сортирует последовательность S размера n в O (n log n) время, предполагая, что два элемента S можно сравнить в O (1) времени.

Answer 6

Рекурсивное дерево будет иметь глубину log(N), и на каждом уровне в этом дереве вы будете выполнять комбинированную N работу по объединению двух отсортированных массивов.

Объединение отсортированных массивов

Чтобы объединить два отсортированных массива A[1,5] и B[3,4], вы просто повторяете оба, начиная с начала, выбирая самый нижний элемент между двумя массивами и увеличивая указатель для этого массива. Вы закончите, когда оба указателя достигнут конца своих соответствующих массивов.

[1,5] [3,4]  --> []
 ^     ^

[1,5] [3,4]  --> [1]
   ^   ^

[1,5] [3,4]  --> [1,3]
   ^     ^

[1,5] [3,4]  --> [1,3,4]
   ^      x

[1,5] [3,4]  --> [1,3,4,5]
    x     x

Runtime = O(A + B)

Иллюстрация сортировки слиянием

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

beginning with [1,5,3,4], N = 4, depth k = log(4) = 2

  [1,5]    [3,4]     depth = k-1 (2^1 nodes) * (N/2^1 values to merge per node) == N
[1]  [5]  [3]  [4]   depth = k   (2^2 nodes) * (N/2^2 values to merge per node) == N

Таким образом, вы выполняете N работу на каждом из k уровней в дереве, где k = log(N)

N * k = N * log(N)

Answer 7

Многие другие ответы великолепны, но я не видел упоминаний высота и глубина , связанных с примерами "дерева сортировки слиянием".Вот еще один способ подойти к вопросу с большим вниманием к дереву.Вот еще одно изображение, которое поможет объяснить:

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

Вот где начинается глубина дерева. Если n - общий размер исходной последовательности, размер последовательности в любом узле равен n / 2 ⁱ , где i - глубина.Это показано на изображении выше.Соединяя это с линейным объемом работы для каждого среза, у нас есть время выполнения O (n / 2 ⁱ ) для каждого узла в дереве.Теперь нам нужно просто подвести итог для n узлов.Один из способов сделать это - признать, что на каждом уровне глубины дерева есть 2 ⁱ узлов.Таким образом, для любого уровня у нас есть O (2 ⁱ * n / 2 ⁱ ), то есть O (n), потому что мы можем отменить 2 ⁱ s!Если каждая глубина равна O (n), мы просто должны умножить ее на height этого двоичного дерева, которое является logn.Ответ: O (nlogn)

ссылка: Структуры данных и алгоритмы в Python

Answer 8

Алгоритм MergeSort состоит из трех шагов:

1. Деление * Шаг 1005 * вычисляет среднее положение подмассива и занимает постоянное время O (1).
2. Завоевание шаг рекурсивной сортировки двух суб-массивов по n / 2 элементов в каждом.
3. Объединить шаг объединяет в общей сложности n элементов за каждый проход, требующий не более n сравнений, поэтому требуется O (n).

Алгоритм требует приблизительно logn проходов для сортировки массива из n элементов, поэтому общая сложность времени равна nlogn.