Докажите время выполнения оптимизированной сортировки слиянием - тета (NK + Nlog (N / K))?

Question

Хорошо, я знаю, что Mergesort имеет наихудшее время тета (NlogN), но его издержки высоки и проявляются в нижней части дерева рекурсии, где производятся слияния. Кто-то предложил остановить рекурсию, как только размер достигнет K, и переключиться на сортировку вставки в этой точке. Мне нужно доказать, что время выполнения этого модифицированного рекуррентного отношения - тета (NK + Nlog (N / k))? Я не понимаю, как подойти к этой проблеме ..

Answer 1

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

T(N) = 2 * T(N / 2) + N

, т.е. вы делите задачу на 2 подзадачи половинного размера, а затем выполняете работу N (слияние).У нас есть базовый случай, который требует постоянного времени.

Моделирование этого дерева, которое у нас есть:

T(N)   =   N   ->   T(N / 2)   
               ->   T(N / 2)

       =   N   ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)
               ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)

Это дает расширение

T(N) = N + 2N/2 + 4N/4 + ...
     = N + N + N ...

Так что на самом деле мыпросто нужно посмотреть, как глубоко это заходит.Мы знаем, что i-й уровень работает с подзадачами размером N / 2^i.Таким образом, наши конечные узлы (T(1)) находятся на уровне L, где N / 2^L = 1:

N / 2^L = 1
N = 2^L
log N = log(2^L)
log N = L

Итак, наше время выполнения равно N log N.

Теперь мы вводим сортировку вставкой.Наше дерево будет выглядеть примерно так:

T(N) = ... -> I(K)
           -> I(K)
             ...x N/K

Другими словами, на каком-то уровне L придется решить N/K проблемы сортировки вставки размером K.Сортировка вставки имеет худшее время выполнения K^2.Таким образом, на листьях у нас много работы в общей сложности :

(N / K) * I(K)
= (N / K) * K * K
= N * K

Но у нас также есть куча слияний по цене N за уровеньдерево, как объяснено ранее.Возвращаясь к нашему предыдущему методу, давайте найдем L (количество уровней, прежде чем мы достигнем подзадач размером K и, таким образом, переключимся на вставку):

N / 2^L = K
N / K = 2^L
L = log (N/K)

Таким образом, в общей сложности мы имеем

O(N) = N * K + N * log (N/K)

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