Докажите, что максимальное сравнение двоичной кучи сборки составляет (2n-2)

Я пытаюсь доказать, что для двоичных куч buildHeap выполняет не более (2N-2) сравнений между элементами. Мне очень трудно доказать это утверждение.

что ты уже испробовал?

ilim 11.04.2018 16:29

Я понял всю сложность бегового времени. Sum h = 0 -> Log N | (п / 2 ^ (ч + 1)) * O (H)

Izik 11.04.2018 17:13

Нет, это не дубликат, я не говорю о временной сложности, мой вопрос относится к количеству сравнений.

Izik 12.04.2018 11:30

Вопрос может быть в другом, да. Тем не менее, анализ сложности включает подсчет количества сравнений. Фактически, если вы обратитесь к ответу на этот вопрос, он будет очень похож, если не более подробным, чем ответ на ваш вопрос.

ilim 12.04.2018 11:35
5
5
3 108
1

Ответы 1

Алгоритм построения кучи начинается с середины и перемещает элементы вниз по мере необходимости. Рассмотрим кучу из 127 элементов (7 уровней). В худшем случае:

64 nodes (the leaf level) don't move at all
32 nodes move down one level
16 nodes move down two levels
 8 nodes move down three levels
 4 nodes move down four levels
 2 nodes move down five levels
 1 node moves down six levels

Так что в худшем случае у вас есть

64*0 + 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6
0 + 32 + 32 + 24 + 16 + 10 + 6 = 120 swaps

Таким образом, в худшем случае build-heap выполняет меньше N свопов.

Поскольку build-heap требует, чтобы вы поменяли местами элемент с наименьшим из его дочерних элементов, для инициирования обмена требуется два сравнения: одно, чтобы найти наименьшего из двух дочерних элементов, и одно, чтобы определить, больше ли узел и должен ли он быть заменен.

Число сравнений, необходимых для перемещения узла, равно 2*(levels_moved+1), и не более N / 2 узлов будут перемещены.

Общий случай

Нам нужно доказать, что максимальное количество сравнений не более 2N-2. Как я отмечал выше, требуется два сравнения, чтобы переместить узел на один уровень. Таким образом, если количество перемещенных уровней меньше N (т.е. (N-1) или меньше), то максимальное количество сравнений не может превышать 2N-2.

Я использую полную кучу в обсуждении ниже, потому что это наихудший случай.

В полной куче из N элементов имеется (N + 1) / 2 узлов на уровне листа. (N + 1) / 4 на следующий уровень выше. (N + 1) / 8 на следующем и т. Д. Вы получите следующее:

(N+1)/2 nodes move 0 levels
(N+1)/4 nodes move 1 level
(N+1)/8 nodes move 2 levels
(N+1)/16 nodes move 3 levels
(N+1)/32 nodes move 4 levels
...

Это дает нам серию:

((N+1)/2)*0 + ((N+1)/4)*1 + ((N+1)/8)*2 + ((N+1)/16)*3 ...

Посмотрим, что это значит для куч разного размера:

heap size  levels   levels moved
   1         1          0
   3         2          1
   7         3          2*1 + 1*2 = 4
   15        4          4*1 + 2*2 + 1*3 = 11
   31        5          8*1 + 4*2 + 2*3 + 1*4 = 26
   63        6          16*1 + 8*2 + 4*3 + 2*4 + 1*5 = 57
   127       7          32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 = 120
         ....

Я выполнил это для кучи до 20 уровней (размер миллион и изменение), и это верно: максимальное количество перемещаемых уровней для полной кучи из N элементов составляет N-log2 (N + 1).

Принимая вышеуказанный ряд как Аритетико-геометрическая последовательность, мы вычисляем сумму для членов log2(N + 1) - 1, игнорируя первый член, поскольку он равен нулю, чтобы она была равна N - 1. (Напомним, что полное двоичное дерево имеет уровни log2(N + 1))

Эта сумма представляет собой общее количество раз, когда выполнялась операция фильтрации. Таким образом, общее количество требуемых сравнений составляет 2N - 2 (поскольку каждая операция просеивания требует двух сравнений). Это также верхняя граница, поскольку полное двоичное дерево всегда представляет наихудший случай для заданной глубины дерева.

может я что-то пропустил, но не понимаю, почему 2 * (levels_moved + 1) = 2n-2.

Izik 15.04.2018 09:25

@Izik Да, я думаю, тебе что-то не хватает. Если вы знаете, что build-heap всегда делает меньше, чем N перемещений уровней (т.е. levels_moved <= (N-1)), и для каждого перемещения уровня требуется не более 2 сравнений, тогда максимальное количество сравнений - 2*(N-1), что равно 2N-2.

Jim Mischel 16.04.2018 02:45

@JimMischel Я могу понять, почему количество уровней, перемещенных для элементов полной кучи, равно N-log2 (N + 1), но я не понимаю, что вы делали дальше ... как вы рассчитали серию? как получилось N-1? вы можете показать свою формулу? также вы можете видеть, что если у вас есть полная куча, например, с 7 узлами, максимальное количество сравнений составляет 8 .. и 2 * 7-2 = 12 .. есть кое-что, что я здесь не понимаю :(

t0nty 06.04.2019 20:10

@ t0nty Исходная постановка задачи: Докажите, что максимальное количество сравнений не более 2N-2. Итак, мы должны доказать, что максимальное количество ходов для одного из 7 элементов не превышает 12. Вы сами сказали, что действительное число равно 8. 8 не больше 12. В чем проблема ?

Jim Mischel 09.04.2019 05:51

О, я понял .. А как насчет суммы, которую ты сделал? Я не понимаю, как в итоге дошло до N-1?

t0nty 10.04.2019 23:38

@ t0nty Вы должны быть более точными. На первом примере я показал, что куча из 127 элементов может заменить не более 120 элементов.

Jim Mischel 11.04.2019 03:24

Я имею в виду, как вы вычислили Аритетико-геометрическую Последовательность? и ПОЧЕМУ с этой суммой?

t0nty 12.04.2019 00:34

Другие вопросы по теме