Каково рекуррентное уравнение для этого алгоритма умножения?

Question

Алгоритм умножения для умножения числа г два Radix:

0 <= x,y < r^n 
x = x1 * r^(n/2) + x0 
y = y1 * r^(n/2) + y0 

, где x0 это половина x, что содержит младшие цифры, и x1 составляет половину с наиболее значащими цифрами, и аналогичен для y.

Так что если r = 10 и n = 4, у нас есть x = 9723 = 97 * 10^2 + 23, где x1 = 97 and x0 = 23.

Умножение может быть сделано как:

z = x*y = x1*y1 + (x0*y1 + x1*y0) + x0*y0 

Таким образом, мы теперь имеем четыре умножений половинного размера чисел (мы первоначально имели умножение п значных чисел, и теперь мы имеем четыре умножений n/2 значные номера).

Как я вижу это повторение для этого алгоритма:

T(n) = O(1) + 4*T(n/2) 

Но, видимо, это T(n) = O(n) + 3T(n/2)

В любом случае, решение T(n) = O(n^2), и я могу видеть это, но мне интересно, почему существует термин O (n) вместо термина O(1)?

Answer 1

Вы правы, если вы вычислите термин x0*y1 + x1*y0 наивно, с двумя продуктами, временная сложность квадратична. Это связано с тем, что мы делаем четыре продукта, и, как вы полагаете, повторяется, T(n) = O(n) + 4T(n/2), который решает до O(n^2).

Однако Карацуба заметил, что xy=z2 * r^n + z1 * r^(n/2) + z0, где мы упустили z2=x1*y2, z0=x0*y0 и z1=x0*y1 + x1*y0, и что можно выразить последний термин, как z1=(x1+x0)(y1+y0)-z2-z0, который включает в себя только один продукт . Используя этот трюк, повторение становится T(n) = O(n) + 3T(n/2), потому что мы делаем три продукта в целом (в отличие от четырех, если не используем трюк).

Поскольку цифры порядка r^n нам понадобятся n цифры для представления чисел (в общем случае, для фиксированного r>=2, нам нужно O(log N) цифры, чтобы представить число N). Чтобы добавить два номера этого ордера, вам нужно «коснуться» всех цифр. Поскольку есть n цифр, вам нужно O(n) (формально я бы сказал Omega(n), что означает «по крайней мере, порядка n времени», но давайте оставим детали в стороне), чтобы вычислить их сумму.

Например, при вычислении продукта N*M, число бит n будет max(log N, log M) (предполагая, что основание r>=2 постоянно).

Алгебраический трюк более подробно поясняется на странице Wiki для Karatsuba algorithm.