Изменения

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

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

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

Навигация