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

Question

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

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

Решение:

Если сортировка выполняется за линейное время для т входных перестановок, то высота Н части дерева решений, состоящее из М соответствующих листьев и их предков линейны. Используйте тот же аргумент, что и в доказательстве теоремы 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

Каждый из этих доказательств являются простой модификацией более общего доказательства того, что вы не можете иметь сравнение сортировки, которая сортирует быстрее, чем Ω (п § п) (вы можете увидеть это доказательство in this earlier answer). Интуитивно, рассуждение идет следующим образом. Чтобы алгоритм сортировки работал правильно, он должен быть способен определить, что такое первоначальный порядок элементов. В противном случае он не может изменить порядок значений, чтобы поместить их в порядке возрастания. Для n элементов существует n! различные перестановки этих элементов, что означает, что существует n! различные входные данные для алгоритма сортировки.

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

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

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

Однако, вы можете сортировать 2 ^п перестановок в линейном времени, так как Lg 2 ^п = п = О (п).

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