Более жесткая связь на heapify

Question

Я хочу вычислить более жесткую границу для heapify, используя подход siftdown, поэтому я действовал следующим образом:

На каждом уровне i каждая клавиша на этом уровне может перейти на конечный уровень h (где hэто высота дерева) в худшем случае.
Поскольку на уровне i есть 2 ⁱ узлов, итого выполненная работа составляет

∑ _0≤i≤h (h - i) * 2 ⁱ

Но я не мог идти дальше.Я знаю, что это должно прийти O (n), но я не мог достичь этого.Пожалуйста, помогите мне решить эту проблему.

Answer 1

S = ∑ _0≤i≤h (h - i) * 2 ⁱ

S = h + 2 (h - 1) + 4 (ч - 2) + ... + 2 ^{ч - 1} ... (1)

Умножить обе стороны на 2,

2S = 2 ч + 4 (ч- 1) + 8 (ч - 2) + ... + 2 ^ч ... (2)

Вычесть из (1) из (2),

S = h -2h + 2 + 4 + 8 +….+ 2 ^ч

= -ч - 1 + (1 + 2 + 4 + 8 +… + 2 ^ч )

= (2 ^{ч + 1} - 1) - (ч + 1)

[Примечание: 1 + 2 + 4 + 8 + ... + 2 ^ч = (2 ^{h + 1} - 1)

Поскольку полное двоичное дерево высотой h имеет от 2h до 2h + 1 узлов, сумма выше равна O (n), где n - количество узловв кучу.

Answer 2

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

∑ i * 2 ^h-i

= 2 ^ч * ∑ i / 2 ⁱ

= 2 ^ч * O (1)

= O (2 ^logn ) = O (n)

Я поменял h на logn, так как это двоичная куча.

Я объясню, почему эта сумма равна O (1):

Сумма является конечной суммой слагаемых i / 2 ⁱ , поэтому, если мы покажем сходимость бесконечной суммы (i -> бесконечная), то, очевидно, каждая конечная сумма (т.е. для всех n) будет суммировать меньше, чем это значение (так как все условия являются положительными). Значение каждой конечной суммы ограничено константой, т. Е. O (1).

Нам остается только доказательство того, что бесконечность ∑ i / 2 ⁱ сходится. Мы можем использовать множество тестов сходимости, давайте воспользуемся простым результатом, что i 1 / i ² сходится и покажем, что для достаточно большого i будет верхняя граница нашей суммы:

Мы хотим показать, что для достаточно большого я:

i / 2 ⁱ <1 / i <sup>2

, что происходит, если i ³ <2 <sup>i , что верно, скажем, для i> 10

КЭД