Изменения

Перейти к: навигация, поиск

Дерево Уоллеса

26 байт добавлено, 14:26, 7 января 2017
Схемная сложность
Каждый элемент <tex>3\to2</tex> имеет глубину <tex>O(1)</tex> и размер <tex>O(n)</tex>.
Подсчитаем количество элементов <tex>3\to2</tex>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается в полтора раза. Тогда глубина дерева будет равна <tex>\log_{3/2}n</tex>, и в нём будет <texdpi=140>{\Huge n + \frac23n frac{2}{3} n + \left(\frac23frac{2}{3}\right)^2n + \ldots = O(n)}</tex> элементов <tex>3\to2</tex>.
Тогда общая сложность равна
<texdpi=140>depth = depth_{3\to2} \cdot \log_{3/2}n + depth_{sum} = O(\log n)</tex>
<texdpi=140>size = size_{3\to2} \cdot O(n) + size_{sum} = O(n^2) </tex>
== Смотри также ==
35
правок

Навигация