Глубокое понимание временной сложности с сортировкой по куче

Предполагая, что вам разрешено узнать об относительном ранжировании двух объектов только путем их сравнения, тогда нет способа удалить все элементы из двоичной кучи за время O (n). Если бы вы могли это сделать, вы могли бы отсортировать список за время O (n), построив кучу за время O (n), а затем удалив все из очереди за время O (n). Однако нижняя граница сортировки говорит о том, что сортировки сравнения, чтобы быть правильными, должны иметь время выполнения в среднем (n log n). Другими словами, вы не можете извлекать из кучи слишком быстро, иначе вы сломаете барьер сортировки.

Также возникает вопрос, почему удаление n элементов из двоичной кучи занимает время O (n log n), а не что-то более быстрое. Это немного сложно показать, но вот основная идея. Рассмотрим первую половину удалений, которые вы делаете в куче. Посмотрите на значения, которые фактически были исключены из очереди, и подумайте, где они были в куче для начала. За исключением тех, что в нижнем ряду, все остальное, что было исключено из очереди, должно было перетекать в верхнюю часть кучи по одному свопу за раз, чтобы быть удаленным. Вы можете показать, что в куче достаточно элементов, чтобы гарантировать, что только на это потребуется время (n log n), потому что примерно половина этих узлов будет глубоко в дереве. Это объясняет, почему амортизированный аргумент не работает - вы постоянно вытягиваете глубокие узлы в кучу, поэтому общее расстояние, которое должны пройти узлы, велико. Сравните это с операцией heapify, когда большинство узлов перемещаются на очень небольшое расстояние.

Позвольте мне показать вам математически, как мы можем вычислить сложность преобразования произвольного массива в кучу (позвольте мне назвать эту сборку кучи) и последующей сортировки с помощью heapsort.

Анализ времени сборки кучи

Чтобы преобразовать массив в кучу, мы должны посмотреть на каждый узел с дочерними элементами и скопировать (утопить) этот узел. Вы должны спросить себя, сколько сравнений мы выполняем; если вы подумаете, то увидите, что (h = высота дерева):

• Для каждого узла на уровне i мы проводим сравнение h-i: #comparesOneNode (i) = h-i
• На уровне i у нас есть 2 ^ i узлов: #nodes (i) = 2 ^ i
• Итак, обычно T (n, i) = #nodes (i) * #comparesOneNode (i) = 2 ^ i * (h-i), время, затрачиваемое на сравнения на уровне i.

Приведем пример. Предположим, у вас есть массив из 15 элементов, т.е. высота дерева будет h = log2 (15) = 3:

• На уровне i = 3 у нас есть 2 ^ 3 = 8 узлов, и мы делаем 3–3 сравнения для каждого узла: правильно, поскольку на уровне 3 у нас есть только узлы без дочерних узлов, то есть листья. Т (п, 3) = 2 ^ 3 * (3-3) = 0
• На уровне i = 2 у нас есть 2 ^ 2 = 4 узла, и мы делаем 3–2 сравнения для каждого узла: правильно, поскольку на уровне 2 у нас есть только уровень 3, с которым мы можем сравнивать. Т (п, 2) = 2 ^ 2 * (3-2) = 4 * 1
• На уровне i = 1 у нас есть 2 ^ 1 = 2 узла, и мы делаем 3-1 сравнения для каждого узла: T (n, 1) = 2 ^ 1 * (3-1) = 2 * 2
• На уровне i = 0 у нас есть 2 ^ 0 = 1 узел, корень, и мы делаем 3-0 сравнений: T (n, 0) = 2 ^ 0 * (3-0) = 1 * 3

Хорошо, в общем:

Т (п) = сумма (я = от 0 до ч) 2 ^ я * (ч-я)

но если вы помните, что h = log2 (n), мы имеем

T (n) = сумма (от i = 0 до log2 (n)) 2 ^ i * (log2 (n) - i) = ~ 2n

Анализ времени heapsort

Здесь анализ действительно похож. Каждый раз, когда мы удаляем максимальный элемент (корень), мы переходим к корню последнего листа в дереве, добавляем его в кучу и повторяем до конца. Итак, сколько сравнений мы проводим здесь?

• На уровне i у нас есть 2 ^ i узлов: #nodes (i) = 2 ^ i
• Для каждого узла на уровне i, heapify, в худшем случае, всегда будет делать то же количество сравнений, которое точно равно уровню i (мы берем один узел с уровня i, перемещаем его в корневой каталог, вызываем heapify и heapify в в худшем случае узел вернется на уровень i, выполняется сравнение i): #comparesOneNode (i) = i
• Итак, обычно T (n, i) = #nodes (i) * #comparesOneNode (i) = 2 ^ i * i, время, затрачиваемое на удаление первых 2 ^ i корней и возвращение в правильное положение временных корней .

Приведем пример. Предположим, у вас есть массив из 15 элементов, т.е. высота дерева будет h = log2 (15) = 3:

• На уровне i = 3 у нас есть 2 ^ 3 = 8 узлов, и нам нужно переместить каждый из них в корневое место, а затем скопировать каждый из них. Каждый heapify будет работать в худшем случае, который я сравниваю, потому что корень может опуститься до все еще существующего уровня i. Т (п, 3) = 2 ^ 3 * 3 = 8 * 3
• На уровне i = 2 у нас есть 2 ^ 2 = 4 узла, и мы делаем 2 сравнения для каждого узла: T (n, 2) = 2 ^ 2 * 2 = 4 * 2
• На уровне i = 1 у нас есть 2 ^ 1 = 2 узла, и мы делаем 1 сравнение для каждого узла: T (n, 1) = 2 ^ 1 * 1 = 2 * 1
• На уровне i = 0 у нас есть 2 ^ 0 = 1 узел, корень, и мы делаем 0 сравнений: T (n, 0) = 0

Хорошо, в общем:

Т (п) = сумма (я = от 0 до ч) 2 ^ я * я

но если вы помните, что h = log2 (n), мы имеем

T (n) = сумма (от i = 0 до log2 (n)) 2 ^ i * i = ~ 2nlogn

Сборка кучи VS heapsort

Интуитивно вы можете видеть, что heapsort не может амортизировать свои затраты, потому что каждый раз, когда мы увеличиваем количество узлов, нам нужно делать больше сравнений, в то время как у нас есть прямо противоположное в функциональности сборки кучи! Вы можете увидеть здесь:

• Сборка кучи: T (n, i) ~ 2 ^ i * (h-i), если i увеличивается, # узлов увеличивается, но # сравнивает уменьшается
• Heapsort: T (n, i) ~ 2 ^ i * i, если i увеличивается, # количество узлов увеличивается, а #compares увеличивается

So:

• Уровень i = 3, #nodes (3) = 8, Heap build выполняет 0 сравнений, heapsort выполняет 8 * 3 = 24 сравнения
• Уровень i = 2, #nodes (2) = 4, Heap build выполняет 4 сравнения, heapsort выполняет 4 * 2 = 8 сравнений
• Уровень i = 1, #nodes (1) = 2, Heap build выполняет 4 сравнения, heapsort выполняет 2 * 1 = 2 сравнения
• Уровень i = 0, #nodes (0) = 1, сборка кучи выполняет 3 сравнения, heapsort выполняет 1 * 0 = 1 сравнивает