Докажите время выполнения оптимизированного Mergesort - это Theta (NK + NLOG (N/K))?

Question

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

Answer 1

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

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Уровень TH работает на подпрозрачных средствах 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)

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