668
правок
Изменения
→Построение кучи за O(N)
|proof=
Обозначим за <tex>S</tex> сумму ряда. Заметим, что
<tex dpi = "160"> \frac{hn}{D^hn} = \frac{1}{D} \cdot \frac{n - 1}{D ^{n - 1}} + \frac{1}{D^n}. </tex>
<tex dpi = "160">{\sum_{n = 1}^\infty \limits}\frac{1}{d^n}</tex> {{---}} это сумма бесконечной убывающей геометрической прогрессии, и она равна <tex dpi = "160">
