Может кто-нибудь объяснить мне простым языком или просто объяснить это?
Почему слияние сортируется в худшем случае времени выполнения O (n log n)?
Ответ 1
В "традиционном" сортировке слияния каждый проход через данные удваивает размер отсортированных подразделов. После первого прохода файл будет отсортирован на разделы длиной два. После второго прохода длина четыре. Затем восемь, шестнадцать и т.д. До размера файла.
Необходимо удвоить размер отсортированных разделов, пока не будет один раздел, содержащий весь файл. Для достижения размера файла потребуется lg (N) удвоения размера раздела, и каждый проход данных займет время, пропорциональное количеству записей.
Ответ 2
Сортировка слияния использует метод Разделить и защищать для решения проблемы сортировки. Во-первых, он делит вход пополам с помощью рекурсии. После деления он сортирует половинки и объединяет их в один отсортированный вывод. См. Рисунок
Это означает, что лучше сначала отсортировать половину своей проблемы и выполнить простую процедуру слияния. Поэтому важно знать сложность подпрограммы слияния и сколько раз она будет вызываться в рекурсии.
Псевдокод для сортировки слияния действительно прост.
# 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 ++, я ++ или j ++, if утверждение и атрибуция C = A | B. Таким образом, у вас будет меньше или равно 4N + 2 операций, дающих сложность O (N). Для доказательства 4N + 2 будем рассматривать как 6N, так как верно для N = 1 (4N +2 <= 6N).
Итак, предположим, что у вас есть вход с элементами 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)
Литература:
Ответ 3
Это связано с тем, что в случае худшего случая или среднего случая сортировка слияния просто делит массив на две половины на каждом этапе, который дает ему компонент lg (n), а другой компонент N - из его сравнений, которые выполняются на каждом этапе, Поэтому объединение его становится почти O (nlg n). Независимо от того, является ли средний случай или худший случай, всегда присутствует коэффициент lg (n). Фактор остатка N зависит от сравнений, сделанных в результате сравнений, выполненных в обоих случаях. В худшем случае это тот, в котором N сравнений происходит для ввода N на каждом этапе. Таким образом, он становится O (nlg n).
Ответ 4
После разделения массива на сцену, где у вас есть отдельные элементы, то есть вызовите их подписок,
-
на каждом этапе мы сравниваем элементы каждого подсписка с его смежным подсписком. Например, [Повторное использование изображения @Davi ]
![введите описание изображения здесь]()
- На этапе 1 каждый элемент сравнивается с его смежным, поэтому n/2 сравнения.
- На этапе-2 каждый элемент подсписок сравнивается с его смежным подсписком, поскольку каждый подсписчик сортируется, это означает, что максимальное количество сравнений между двумя подсписками равно <= длина подписок, т.е. 2 (на этапе -2) и 4 сравнения на этапах 3 и 8 на этапе-4, поскольку подсписки сохраняют удвоение по длине. Это означает максимальное количество сравнений на каждом этапе = (длина подписок * (количество подписок /2)) == > n/2
- Как вы заметили, общее количество этапов будет "log (n)" Таким образом, общая сложность будет == (максимальное количество сравнений на каждом этапе * количество этапов) == O ((n/2) * log (n)) == > O (nlog (n))
Ответ 5
Алгоритм MergeSort выполняет три шага:
- Разделить шаг вычисляет среднее положение суб-массива и принимает постоянное время O (1).
- Conquer шаг рекурсивно сортирует два вспомогательных массива приблизительно из n/2 элементов.
- Объединить шаг объединяет в общей сложности n элементов на каждом проходе, требующих не более n сравнений, поэтому он принимает O (n).
Для алгоритма требуются прокси-протоколы для сортировки массива из n элементов, поэтому общая временная сложность nlogn.
Ответ 6
Многие из других ответов велики, но я не видел упоминания о высоте и глубине, связанных с примерами дерева сортировки. Вот еще один способ приблизиться к вопросу с большим вниманием к дереву. Вот еще одно изображение, которое поможет объяснить:
Просто повторение: как указывали другие ответы, мы знаем, что работа слияния двух отсортированных фрагментов последовательности выполняется в линейном времени (вспомогательная функция слияния, которую мы вызываем из основной функции сортировки).
Теперь, глядя на это дерево, где мы можем думать о каждом потомке корня (кроме корня) в качестве рекурсивного вызова функции сортировки, попробуйте оценить, сколько времени мы тратим на каждый node... Поскольку нарезка последовательности и слияние (оба вместе) принимают линейное время, время работы любого node является линейным относительно длины последовательности при этом node.
Здесь, где глубина дерева приходит. Если n - это общий размер исходной последовательности, размер последовательности в любом node равен n/2 i где я - глубина. Это показано на изображении выше. Объединяя это вместе с линейным объемом работы для каждого среза, у нас есть время работы O (n/2 i) для каждого node в дереве. Теперь нам просто нужно суммировать это для n узлов. Один из способов сделать это - признать, что на каждом уровне глубины дерева есть 2 i узла. Итак, для любого уровня имеем O (2 i * n/2 i), что является O (n), потому что мы можем отменить 2 i s! Если каждая глубина равна O (n), нам просто нужно умножить ее на высоту этого двоичного дерева, которое является logn. Ответ: O (nlogn)