35
правок
Изменения
Нет описания правки
===Элемент 3→2===
[[file:3→23v2.png|thumb|300px|Элемент 3→2]]
Для того, чтобы представить сумму трёх чисел с помощью двух чисел, воспользуемся полным сумматором. Для каждого <tex>i</tex> направим <tex>x_i</tex>, <tex>y_i</tex> и <tex>z_i</tex> на вход полного сумматора. Тогда младший бит сумматора будет <tex>i</tex>-ым битом первого числа, а старший {{---}} <tex>(i + 1)</tex>-ым второго.
Каждый элемент <tex>3\to2</tex> имеет глубину <tex>O(1)</tex> и размер <tex>O(n)</tex>.
Подсчитаем количество элементов <tex>3\to2</tex>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается в полтора раза. Тогда глубина дерева будет равна <tex>\log_{3/2}n</tex>, и в нём будет <tex>{\Huge n + \frac23n + \left(\frac23\right)^2n + \ldots = O(n)}</tex> элементов <tex>3\to2</tex>.
Тогда общая сложность равна
