Время умножения двух n-разраядных чисел

[Orkimed]

Здравствуйте. Углубляю свои знания в дискретной математике. В книге Окулова случился затык. Никак не получается с ним справиться.
Вот что он пишет:
Пусть a и b - n-разрядные двоичные числа и n является степенью двойки. Тогда $a\cdot b = x_1 \cdot y_1\cdot 2^{n} + (x_1\cdot y_2+x_2\cdot y_1)\cdot 2^{\frac{n}{2}}+x_2\cdot y_2$. Введём следующие обозначения: $t=(x_1+x_2)\cdot(y_1+y_2);\quad v=x_1\cdot y_2;\quad w=x_2\cdot y_2.$ Примет вид : $a\cdot b = v\cdot 2^{n} + (t-v-w)\cdot 2^{\frac{n}{2}}+w$. Следовательно, время умножения двух n-разрядных чисел можно выразить так:

$$\begin{cases} k,&\text{при $n=1$;}\\ 3T(n/2)+kn,&\text{при $n>1$,}\\ \end{cases}$$

где k - постоянное время выполнения операции сложения и сдвигов. Решение уравнения есть $T(n)=3kn^{\log{3}}-2kn$
Вопросы:
Как он получил оценку времени умножения и решение уравнения?

[DeBill]

Orkimed в сообщении #1124923 писал(а):

Как он получил оценку времени умножения

Не очень понятно, что есть $k$...
Было: три умножения маленьких чисе (нашли $t,v,w$). А также : 2 сдвига и несколько сложений-вычитаний (обозначим их кол-во через $K$. Пусть $T(n)$ - время вычисления призведения ( для суммы-сдвига-вычитания оно равно $c\cdot n$ ). Тогда : $T(n) = 3\cdot T(\frac{n}{2}) + K\cdot cn$
Это (почти) и есть Ваше уравнение.
Решается полученное уравнение - как дифуры: только сначала надо сделать подстановку $n=2^x$ и замену $T(2^x) =y(x)$. Получится линейное неоднородное уравнение на функцию $y(x)$:

$y(x) = 3\cdot y(x-1) + k\cdot 2^x$

Решаете однородное уравнение, а затем - методом вариации постоянной - неоднородное....

[Orkimed]

DeBill
Большое спасибо за объяснение. Теперь всё стало понятно.