Вставка сортировки для небольших подмассивов в слиянием

Question

я застрял при решении проблемы в «Введение в алгоритмы по Cormen», проблема заключается в следующем,

Вставка сортировки в небольших массивах сортировки слиянием

Хотя слияния сортировка выполняется в O (n logn) в худшем случае, а сортировка вставки выполняется в O (n^2), последняя выполняется быстрее для небольших размеров проблем. Рассмотрим модификацию Merge Sort, в которой n/k подсписок длины k сортируются с использованием сортировки вставки, а затем объединяются с использованием стандартного механизма слияния.

Чтобы отсортировать п/к подсписки длины к это занимает O (NK) и объединить эти п/к югу списков он принимает O (N Л.Г. (п/к))

Таким образом, модифицированный алгоритм принимает O (nk) + O (n lg (n/k)),

Что такое наибольшее асимптотическое (Θnotation) значение k как функция n, для которого модифицированный алгоритм имеет такое же асимптотическое время работы, как и стандартное слияние Сортировать?

Как следует выбирать на практике?

Это две вещи, где я застрял, любая помощь приветствуется, спасибо заранее :)

Answer 1

Первый вопрос задает, по существу, может быть K больше или равно Lg п и до сих пор имеют асимптотический порядок Θ (n lg n). Если это больше, мы знаем, что комбинация двух алгоритмов сортировки не так эффективна, как просто сортировка слияния. Итак, предположим, что k = Θ (lg n). Если вы подключите lg n, где k находится в вашем рекуррентном соотношении, так что T (nlgn + n lg (n/lg (n)) и решит, что вы будете иметь наибольшую асимптотическую величину в Θnotation.

Что касается того, как K выбирается, k должен быть максимальным размером ввода, на котором сортировка вставки быстрее, чем слияние. Если мы добавим некоторые положительные целые числа к nk и nlgn, мы знаем, что k зависит от отношения между этими двумя положительными целыми числами. Надеюсь, это поможет!

ех XNK + ynlgn

х и у положительные константы

так, к = х/у, потому, что сводит к минимуму AB ove выражение. Таким образом, k не зависит от n.

Answer 2

Извините за опоздание, но я думаю, что могу добавить дополнительную информацию о вашем втором вопросе. Согласно алгоритмов (4-е издание) книги, написанные Роберт Седжвик и Кевин Уэйн

Переключение на сортировку вставками для небольших подмассивов (длина 15 или меньше, скажем) улучшит ход> время типичной реализации сортировки слиянием путем От 10 до 15 процентов.