algorithm - 这个乘法算法的递归方程是什么？

Question

乘法算法是将两个基数r相乘:

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 和 x0 = 23。

乘法可以这样完成:

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

所以我们现在有四个半角数字的乘法(我们最初有一个 n 位数字的乘法，现在我们有四个 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)。

但是，Karatsuba 观察到 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 是常量)。

代数技巧在 Karatsuba algorithm 的 Wiki 页面上有更详细的解释。 .