Докажите, что максимальное сравнение двоичной кучи сборки составляет (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
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
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

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