Нижние границы сортировок сравнения для небольшой доли входных данных?

Question

Может кто-нибудь подскажет мне математическую часть решения следующей задачи.

Показать, что не существует сортировки сравнения, у которой время выполнения линейно хотя бы на половину из п! входы длины n. Как насчет доли 1 / n входов длины n? Как насчет дроби (1 / (2) ^ n)?

Решение:

Если сортировка выполняется за линейное время для m входных перестановок, то высота h часть дерева решений, состоящая из m соответствующих листьев и их предки линейны. Используйте тот же аргумент, что и в доказательстве теоремы 8.1, чтобы показать, что это невозможно для m = n! / 2, n! / n или n! / 2n. Мы имеем 2 ^ h ≥ m, что дает нам h ≥ lgm. Для всех возможных мс, приведенных здесь, lgm = Ω (n lg n), следовательно, h = Ω (n lg n). В частности,

    lgn!/2= lg n! − 1 ≥ n lg n − n lg e − 1
    lgn!/n= lg n! − lg n ≥ n lg n − n lg e − lg n
    lgn!/2^n= lg n! − n ≥ n lg n − n lg e − n

Answer 1

Каждое из этих доказательств является прямой модификацией более общего доказательства, что у вас не может быть сортировки сравнения, которая сортируется быстрее, чем & Omega; (n log n) (вы можете увидеть это доказательство в это более ранний ответ ). Интуитивно аргументация выглядит следующим образом. Чтобы алгоритм сортировки работал правильно, он должен быть в состоянии определить, каково начальное упорядочение элементов. В противном случае он не может изменить порядок значений, чтобы расположить их в порядке возрастания. Учитывая n элементов, существует n! различные перестановки этих элементов, а это означает, что есть п! разные входы в алгоритм сортировки.

Первоначально алгоритм ничего не знает о входной последовательности и не может различить ни одно из n! разные перестановки. Каждый раз, когда алгоритм выполняет сравнение, он получает немного больше информации о порядке упорядочения элементов. В частности, он может сказать, находится ли входная перестановка в группе перестановок, где сравнение дает истину, или в группе перестановок, где сравнение дает ложь. Вы можете визуализировать, как алгоритм работает как двоичное дерево, где каждый узел соответствует некоторому состоянию алгоритма, и (до) двух дочерних элементов определенного узла указывают состояния алгоритма, которые будут введены, если сравнение даст значение true или ложь.

Чтобы алгоритм сортировки мог правильно сортировать, он должен иметь возможность вводить уникальное состояние для каждого возможного ввода, так как в противном случае алгоритм не мог бы различить две разные входные последовательности и поэтому сортировал бы по крайней мере один из них неправильно. Это означает, что если вы учитываете количество листовых узлов в дереве (частей, где алгоритм завершил сравнение и собирается сортировать), то на входную перестановку должен быть как минимум один листовой узел. В общем доказательстве есть n! перестановок, поэтому должно быть не менее n! листовые узлы. В двоичном дереве единственный способ иметь k листовых узлов - это иметь высоту, по крайней мере, Omega; (log k), что означает, что вы должны сделать хотя бы сравнение Omega; (log k). Таким образом, общая нижняя граница сортировки в приближении Стирлинга является & Omega; (log n!) = & Omega; (n log n).

В случаях, которые вы рассматриваете, мы ограничиваемся подмножеством этих возможных перестановок. Например, предположим, что мы хотим иметь возможность сортировать n! / 2 перестановок. Это означает, что наше дерево должно иметь высоту не менее lg (n! / 2) = lg n! - 1 = & Omega; (n log n). В следствии. Вы не можете отсортировать по времени O (n), потому что линейная функция не растет со скоростью & Omega; (n log n). Для второй части, посмотрим, сможете ли вы получить n! / n отсортировано по линейному времени, опять же, дерево решений должно иметь высоту lg (n! / n) = lg n! - lg n = & Omega; (n log n), поэтому вы не можете сортировать в O (n) сравнениях. Для финала у нас есть lg n! / 2 ⁿ = lg n! - n = & Omega; (n log n), поэтому, опять же, он не может быть отсортирован за O (n) время.

Однако вы можете отсортировать 2 ⁿ перестановок по линейному времени, поскольку lg 2 ⁿ = n = O (n).

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