Сравнение сортировки - теоретическое

Question

Может ли кто -нибудь объяснить мне решение этой проблемы?

Предположим, что вам дают последовательность не элементы для сортировки. Входная последовательность состоит из n = k подпоследовательности, каждый из которых содержит k элементы. Элементы в данной подпоследовательности все меньше, чем элементы в последующей последующей последовательности и больше, чем элементы в предыдущей подпоследовательности. Таким образом, все, что необходимо для сортировки всей последовательности длины не сортировать k элементы в каждом из n = kподпоследовательности. Показывать n lg k Нижняя граница по количеству сравнений, необходимых для решения этого варианта проблемы сортировки.

Решение:

Позволять С быть последовательностью не элементы разделены на n/k Последствия для каждой длины kгде все элементы в любой последующей последовательности больше, чем все элементы предыдущей подпоследовательности, и меньше, чем все элементы последующей подпоследовательности.

Требовать

Любой алгоритм сортировки на основе сравнения С должен взять (N LG K) время в худшем случае.

Доказательство

Сначала обратите внимание, что, как указано в подсказке, мы не можем доказать нижнюю границу, умножив вместе нижние границы для сортировки каждой последующей последовательности. Это только докажет, что не существует более быстрого алгоритма, который независимо сортирует последствия. Это было не то, что нас просили доказать; Мы не можем ввести дополнительные предположения.

Теперь рассмотрим дерево решений высоты h для любого сорта сравнения для S., поскольку элементы каждой последующей последовательности могут быть в любом порядке, любой из К! Переставации соответствуют окончательному отсортированному порядку последующей. И, поскольку есть n/k Такие последствия, каждая из которых может быть в любом порядке, есть (k!)^N/k перестановки S, которые могут соответствовать сортировке некоторого входного порядка. Таким образом, любое дерево решений для сортировки S должно быть по крайней мере (k!)^N/k листья. Поскольку двоичное дерево высоты часимеет не более чем 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/2 самые большие термины как минимум k/2 каждый. (Мы неявно предполагаем здесь, что k равно. Мы могли бы приспособиться к полам и потолкам, если k были странными.)

Поскольку в любом дереве решений существует как минимум один путь для сортировки S, который имеет длину, по крайней мере, (N/2) LG (K/2), наихудшее время работы любого алгоритма сортировки на основе сравнения для S (N LG K).

Может ли кто -нибудь провести меня через шаги в блоке кода? Особенно шаг, когда LG K! становится LG ((k/2)^k/2).

Answer 1

Я перепечатал математику ниже:

(1) H ≥ lg (k! ^n/k)

(2) = (n/k) lg (k!)

(3) ≥ (N/K) LG ((K/2)^k/2)

(4) = (N/2) LG (K/2)

Давайте пройдемся через это. Переход от строки (1) к строке (2) использует свойства логарифмов. Аналогичным образом, переход от линии (3) к линии (4) использует свойства логарифмов и FACTHTAT (N / K) (K / 2) = (N / 2). Таким образом, шаг трюка переходит от линии (2) к линии (3).

Утверждение здесь следующее:

Для всех k, k! ≥ (K / 2)^{(K / 2)}

Интуитивно, идея заключается в следующем. Подумайте! = k (k - 1) (k - 2) ... (2) (1). Если вы заметите, половина этих условий больше K / 2, и половина из них меньше. Если мы бросим все термины, которые меньше K, мы получим что -то (близкое) следующее:

К! ≥ k (k - 1) (k - 2) ... (K / 2)

Теперь у нас есть k / 2 ≥ k, так что у нас есть это

К! ≥ k (k - 1) (k - 2) ... (k/2) ≥ (k/2) (k/2) ... (K/2)

Это продукт (k / 2) с самим собой (k / 2) раз, поэтому он равен (k / 2)^k/2. Анкет Эта математика не точна, потому что логика для нечетных и даже значений немного отличается, но, по сути, используя эту идею, вы получаете набросок доказательства более раннего результата.

Подводя итог: от (1) до (2) и от (3) до (4) используется свойства логарифмов и от (2) до (3) использует приведенный выше результат.

Надеюсь это поможет!