Может кто-нибудь объяснить мне решение этой проблемы?
Предположим, вам дана последовательность n элементов для сортировки.Входная последовательность состоит из n = k подпоследовательностей, каждая из которых содержит k элементов.Все элементы в данной подпоследовательности все меньше, чем элементы в последующей подпоследовательности, и больше, чем элементы в предыдущей подпоследовательности.Таким образом, все, что необходимо для сортировки всей последовательности длиной n , - это сортировка элементов k в каждой из подпоследовательностей n = k .Покажите n lg k нижнюю границу для числа сравнений, необходимых для решения этого варианта задачи сортировки.
Решение:
Пусть S быть последовательностью n элементов, разделенных на n / k подпоследовательностей, каждая из которых имеет длину k , где все элементы в любой подпоследовательности больше, чем все элементыпредыдущая подпоследовательность и меньшая, чем у всех элементов последующей подпоследовательности.
Заявка
Любой алгоритм сортировки на основе сравнения для сортировки S должен принимать (nLG K) время в худшем случае.
Доказательство
Первое замечание, что, как указано в подсказке, мы не можем доказать нижнюю границу путем умножения нижних границ для сортировкикаждая подпоследовательность.Это только доказало бы, что не существует более быстрого алгоритма, который сортирует подпоследовательности независимо.Это было не то, что мы просим доказать;мы не можем вводить никаких дополнительных предположений.
Теперь рассмотрим дерево решений высоты h для любого вида сравнения для S. Поскольку элементы каждой подпоследовательности могут быть в любом порядке, любой из k! перестановки соответствуют окончательному отсортированному порядку подпоследовательности.И, поскольку существует n / k таких подпоследовательностей, каждая из которых может быть в любом порядке, существует (k!) ^ N / k перестановок S, которые могут соответствоватьсортировка некоторого порядка ввода.Таким образом, любое дерево решений для сортировки S должно иметь как минимум (k!) ^ N / k листьев.Поскольку бинарное дерево высотой h имеет не более 2 ^ h листьев, мы должны иметь 2 ^ h ≥ (k!) ^ (N / k) или h ≥ lg ((k!) ^ n / k) .Таким образом, мы получаем
h ≥ lg((k!)^n/k) -- unbalanced parens - final one added?
= (n/k) lg(k!)
≥ (n/k) lg((k/2)^k/2)
= (n/2) lg(k/2)
Третья строка взята из k! , чьи k / 2 наибольшие слагаемые составляют не менее k / 2 каждый.(Мы неявно предполагаем, что k четно. Мы могли бы отрегулировать по этажам и потолкам, если бы k были нечетными.)
Поскольку в любом дереве решений для сортировки S существует хотя бы один путьимеет длину не менее (n / 2) lg (k / 2) , наихудшее время выполнения любого алгоритма сортировки на основе сравнения для S составляет (n lg k) .
Может ли кто-нибудь провести меня через шаги в блоке кода?Особенно шаг, когда lg k! становится lg ((k / 2) ^ k / 2) .