Кружок - группа A - алгоритм Карацубы

Алгоритм Карацубы позволяет умножить два многочлена или числа длины n за время порядка O(n^log_2(3)) ~ O(n^1.6).

[@user-fx9xc5yf6t]

Очень коротко и понятно!! Спасибо большое!

[@marat0.088]

16:31 - можете объяснить, пожалуйста, почему там (p+q) и (r+s) имеют длину n/2? Там же и вправду может быть перенос разряда. К примеру 5555*5555, тогда по логике: Х = (55+55)*(55+55), а 55+55 =110, а это длина n/2 +1