35
правок
Изменения
→Смотри также
Каждый элемент <tex>3\to2</tex> имеет глубину <tex>O(1)</tex> и размер <tex>O(n)</tex>.
Подсчитаем количество элементов <tex>3\to2</tex>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается в полтора раза. Тогда глубина дерева будет равна <tex>\log_{\frac{3}{2}}n</tex>, и в нём будет <tex> n + \dfrac{2}{3} n + \left(\dfrac{2}{3}\right)^2n + \ldots = O(n)</tex> элементов <tex>3\to2</tex>. Обозначим за <tex>size</tex> общее количество элементов в цепи; за <tex>size_{3\to2}</tex> количество элементов <tex>3\to2</tex>; за <tex>size_{sum}</tex> количесвтво количество элементов матричного двоичного каскадного сумматора в схеме;за <tex>depth</tex> глубину схемы; за <tex>depth_{3\to2}</tex> глубину каждого из элементов <tex>3\to2</tex>; за <tex>depth_{sum}</tex> глубину каждого из элементов двоичного каскадного сумматора.
Тогда общая сложность равна
<tex>size = size_{3\to2} \cdot O(n) + size_{sum} = O(n^2) </tex>
== Смотри См. также ==
* [[Матричный умножитель]]
* [[Сумматор]]
* [[Двоичный каскадный сумматор]]
== Источники информации==
* Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ — 960 с. — ISBN 5-900916-37-5
