304
правки
Изменения
→Схемная сложность
Каждый элемент <tex>3\to2</tex> имеет глубину <tex>O(1)</tex> и размер <tex>O(n)</tex>.
Подсчитаем количество элементов <tex>3\to2</tex>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается в <tex>1{,}5</tex> полтора раза. Тогда глубина дерева будет равна <tex>\log_{3/2}n</tex>, и в нём будет <tex>n + \frac23n + \left(\frac23\right)^2n + \ldots = O(n)</tex> элементов <tex>3\to2</tex>.
Тогда общая сложность равна
