Я пытаюсь доказать, что для двоичных куч buildHeap выполняет не более (2N-2) сравнений между элементами. Мне очень трудно доказать это утверждение.
Я понял всю сложность бегового времени. Sum h = 0 -> Log N | (п / 2 ^ (ч + 1)) * O (H)
Возможный дубликат наихудший случай сложности времени построения кучи по сравнению с верхней границей / жесткой верхней границей
Нет, это не дубликат, я не говорю о временной сложности, мой вопрос относится к количеству сравнений.
Вопрос может быть в другом, да. Тем не менее, анализ сложности включает подсчет количества сравнений. Фактически, если вы обратитесь к ответу на этот вопрос, он будет очень похож, если не более подробным, чем ответ на ваш вопрос.
Алгоритм построения кучи начинается с середины и перемещает элементы вниз по мере необходимости. Рассмотрим кучу из 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 Да, я думаю, тебе что-то не хватает. Если вы знаете, что build-heap
всегда делает меньше, чем N перемещений уровней (т.е. levels_moved <= (N-1)
), и для каждого перемещения уровня требуется не более 2 сравнений, тогда максимальное количество сравнений - 2*(N-1)
, что равно 2N-2
.
@JimMischel Я могу понять, почему количество уровней, перемещенных для элементов полной кучи, равно N-log2 (N + 1), но я не понимаю, что вы делали дальше ... как вы рассчитали серию? как получилось N-1? вы можете показать свою формулу? также вы можете видеть, что если у вас есть полная куча, например, с 7 узлами, максимальное количество сравнений составляет 8 .. и 2 * 7-2 = 12 .. есть кое-что, что я здесь не понимаю :(
@ t0nty Исходная постановка задачи: Докажите, что максимальное количество сравнений не более 2N-2. Итак, мы должны доказать, что максимальное количество ходов для одного из 7 элементов не превышает 12. Вы сами сказали, что действительное число равно 8. 8 не больше 12. В чем проблема ?
О, я понял .. А как насчет суммы, которую ты сделал? Я не понимаю, как в итоге дошло до N-1?
@ t0nty Вы должны быть более точными. На первом примере я показал, что куча из 127 элементов может заменить не более 120 элементов.
Я имею в виду, как вы вычислили Аритетико-геометрическую Последовательность? и ПОЧЕМУ с этой суммой?
что ты уже испробовал?