ожидаемая продолжительность работы гибрида быстрой сортировки и вставки

Question

Я изучаю CLRS 3-е издание, и вот один из самых сложных вопросов, с которыми я столкнулся вместе с ответом как услуга для всех.

7.4-5 Мы можем улучшить время выполнения быстрой сортировки на практике, воспользовавшись преимуществом быстрого времени выполнения сортировки вставкой, когда ее вход «почти» отсортирован.При вызове быстрой сортировки для подмассива, содержащего менее k элементов, пусть он просто возвращается без сортировки подмассива.После того, как вызов верхнего уровня для быстрой сортировки вернется, запустите сортировку вставкой по всему массиву, чтобы завершить процесс сортировки.Утверждают, что этот алгоритм сортировки выполняется в O(nk+nlg(n/k)) ожидаемое время.Как выбрать k, как в теории, так и на практике?

Answer 1

Если вы оцениваете уравнение nlgn > nk + nlog(n/k), вы получите log k > k.Что невозможно.Следовательно, в теории это невозможно.Но на практике существуют постоянные факторы, связанные с сортировкой вставок и быстрой сортировкой.Посмотрите на решение, обсуждаемое в этом pdf .Вы можете обновить свой ответ.,

Answer 2

На самом деле, ответ k = 8.

Алгоритм, который вы получаете, состоит из двух анонимных функций, одна из которых O(nk), а другая O(n lg n/k).Эти анонимные функции скрывают константы среднего регистра.Сортировка вставкой выполняется в среднем за n^2/4 раз, а случайная быстрая сортировка выполняется в среднем 1.386 n lg n.Мы хотим найти значение k, которое минимизирует значение nk/4 + 1.386( n lg n/k ), равное nk/4 + 1.386 n lg n - 1.386 n lg k.Это значит найти максимум функции 1.386 lg k - k/4.Это максимальное значение происходит при k = 8.

Answer 3

Лист имеет равную вероятность быть размером от 1 до k.
Таким образом, ожидаемый размер листа составляет k/2.
Если ожидаемый размер листа k/2, то мы ожидаем n/(k/2)=(2n)/k таких листьев.
Для простоты предположим, что мы ожидаем n/k таких листьев и что ожидаемый размер каждого листа равен k.
Ожидаемое время работы INSERTION-SORT составляет O(n^2).
Мы обнаружили, что в упражнении 5.2-5 и задаче 2-4c.
Таким образом, ожидаемое время использования INSERTION-SORT составляет O((n/k)*(k^2))=O(nk).
Если мы ожидаем, что наши группы разделов будут иметь размер k, тогда ожидается, что высота дерева рекурсии будет lgn-lgk=lg(n/k), так как мы планируем остановить lgk раньше.
На каждом уровне дерева рекурсии выполняется O(n) операций.
Это приводит нас к O(nlg(n/k)).
Мы заключаем, что ожидаемое время работы составляет O(nk+nlg(n/k)).

Теоретически, мы должны выбрать k=lgn, так как таким образом мы получим наилучшее ожидаемое время работы O(nlgn).

На практике мы должны выбрать k для одного из значений около lgn, которое дает нам лучшую производительность, чем просто запуск RANDOMIZED-QUICKSORT.

Во второй части ответа довольно широко используются обозначения big-O, поэтому для более точного выбора k перейдите по ссылке, указанной во втором ответе Анкуша.