Нижняя граница на гепарте?

Ответ 1

Итак, я немного поработал, и похоже, что этот результат на самом деле довольно недавний! Первое доказательство с нижней границей, которое я могу найти, - это с 1992 года, хотя сам гепсорт был изобретен в 1964 году.

Формальное доказательство нижней границы связано с работой Шаффера и Седжуика "Анализ сосудов". Здесь немного перефразированная версия доказательства, которая опускает некоторые технические детали.

Для начала предположим, что n = 2 ^k - 1 для некоторого k, что гарантирует, что мы имеем полную двоичную кучу. Я покажу, как обрабатывать этот случай по отдельности позже. Поскольку у нас есть 2 ^k - 1 элемента, первый проход heapsort, в & Theta; (n), создаст кучу высоты k. Теперь рассмотрим первую половину dequeues из этой кучи, которая удаляет узлы 2 ^k-1 из кучи. Первое ключевое замечание состоит в том, что если вы берете стартовую кучу и затем отмечаете все узлы здесь, которые на самом деле попадают в категорию dequeued, они образуют поддерево кучи (т.е. Каждый node, который получает dequeued, имеет родителя, который также удаляется). Вы можете это увидеть, потому что если бы это было не так, тогда было бы node, чей (более крупный) родительский объект не был удален, хотя сам node был удален, что означает, что значения не соответствуют порядку.

Теперь рассмотрим, как узлы этого дерева распределены по куче. Если вы назовете уровни кучи 0, 1, 2,..., k - 1, тогда будет некоторое количество этих узлов в уровнях 0, 1, 2,..., k - 2 (т.е. все, кроме нижнего уровня дерева). Для того, чтобы эти узлы были удалены из кучи, они должны быть заменены на корень, и они только разворачиваются на один уровень за раз. Это означает, что одним из способов снизить привязку времени выполнения heapsort было бы подсчет количества свопов, необходимых для доведения всех этих значений до корня. Фактически, это именно то, что мы собираемся делать.

Первый вопрос, на который нам нужно ответить, - это то, сколько узлов с наибольшим числом 2 ^k-1 не находятся на нижнем уровне кучи? Мы можем показать, что это не превосходит 2 ^k-2 от противного. Предположим, что по крайней мере 2 ^k-2 + 1 из самых больших узлов на нижнем уровне кучи. Тогда каждый из родителей этих узлов также должен быть большими узлами уровня k - 2. Даже в лучшем случае это означает, что должно быть не менее 2 ^k-3 + 1 больших узлов на уровне k - 2, что означает, что в уровне k - 3 будет по крайней мере 2 ^k-4 + 1 больших узлов и т.д. Суммируя по всем этим узлам, получим, что есть 2 ^k-2 + 2 ^k-3 + 2 ^k-4 +... + 2 ⁰ + k большие узлы. Но это значение строго больше 2 ^k-1 что противоречит тому, что мы работаем только с узлами ^k-1.

Хорошо... теперь мы знаем, что в нижнем слое имеется не более 2 ^k-2 больших узлов. Это означает, что в первых слоях k-2 должно быть не менее 2 ^k-2 больших узлов. Теперь мы спрашиваем: какова сумма по всем этим узлам расстояния от node до корня? Ну, если у нас есть 2 ^k-2 узлы, расположенные где-то в полной куче, то не более 2 ^k-3 из них могут быть в первых k - 3 уровнях, и поэтому на уровне k - 2. найдутся не менее 2 ^k-2 - 2 ^k-3= 2 ^k-3 тяжелых узлов. Следовательно, общее количество свопов, которые необходимо выполнить, составляет не менее (k - 2) 2 ^k-3. Так как n = 2 ^k -1, k = & Theta; (lg n), и поэтому это значение является & Theta; (n lg n) по мере необходимости.

Ответ 2

Простой ответ: Элементы в куче:

1
2
4
8
...
2^[log(n/4)]
and last level has between (1..2^[log(n/2)]) ==> (1,[n/2]) item, (by [] I mean Ceiling not roof)

например, если у вас есть 7 элементов:

1
2
4

и если у вас есть 8 элементов:

1
2
4
1

Существует два разных дерева кучи: сначала по крайней мере n/4 - 1 элемента кучи находятся на последнем уровне или нет, поэтому на последнем уровне по крайней мере n/4 - 1 на уровне до первого. В первом случае это берет O((n/4 - 1) * log(n/2)), чтобы удалить элементы верхнего уровня из кучи, а во втором случае требуется O((n/4 - 1) * log(n/4)) удалить элементы с предыдущего уровня. поэтому в обоих случаях Ω (n log (n)) только для n/4 - 1 элементов, поэтому это нижняя граница (легко можно сказать, что она плотная нижняя граница).

Ответ 3

Вот решение, использующее термины CLRS:
Мы начинаем с max-heap, который является полным двоичным деревом с элементами n.
Можно сказать, что в полном двоичном слое есть n/2 листья и n/2 внутренние узлы.
n/2 итерации HEAP-SORT удаляют наибольшие элементы n/2 из кучи.
Пусть S - множество наибольших элементов n/2.
В листьях может быть не более n/4 элементов из S, так как во внутренних узлах их должно быть дополнительно n/4.
Пусть L - эти n/4 наибольшие элементы из S, которые находятся в листьях.
Поэтому, если есть элементы n/4 из S на уровне 0 (уровень листьев) то они должны быть не менее n/8 из них на уровне 1.
Пусть P - эти элементы n/8 из S, которые находятся на уровне 1.
n/2 итерации HEAP-SORT могут дать элементам от L короткий отрезок к корню а затем из кучи, но элементы из P должны пройти весь путь до корня до их удаления из кучи.
Таким образом, существует не менее (n/8)(lgn-1) операций, что дает нам время работы & Omega; (nlgn).
Теперь для случая максимальной кучи, которая не имеет всех ее листьев на уровне 0.
Пусть k - число его листьев на уровне 0.
После k итераций HEAP-SORT у нас остается макс-куча, которая полное двоичное дерево с высотой lgn-1.
Мы можем продолжить наше доказательство так же. Теперь для случая, когда меньше n/4 выходит из S.
Пусть k - число элементов из S, находящихся в листьях на уровне 0.
Если k <= n/8, то должно быть не менее n/8 элементов из S на уровне 1.
Это связано с тем, что на уровне 1 может быть всего n/4 элементов.
Мы продолжаем доказательство так же. Если k>n/8, то должно быть не менее n/16 элементов из S, находящихся на уровне 1.
Мы продолжаем доказательство так же. Мы заключаем, что время работы HEAP-SORT равно & Omega; (nlgn).