2

在分析算法时，我看到我们通常假设乘法需要单条计算机指令。但是这个假设在数字大小（就位数而言）时并不合适。在最基本的乘法形式中，将两个 n 位数相乘通常是 O(n^2)。在这种情况下，计算 x^n.(x 的 n 次方) 的复杂性（就位操作而言）可能是多少？

使用解释的方法，对我来说复杂性似乎是 n 的指数（但不确定确切的数字）

4

3 回答 3

3

计算的复杂性x^n当然取决于用于计算幂和乘法的算法。如果通过平方计算每个幂的幂，则需要 O(log n) 乘法。在每个步骤中，您要么对一个数字进行平方，要么将两个数字相乘，然后对两者中的一个进行平方。

如果x有d(x)数字，则x^n有 Θ(n*d(x)) 数字，在最后一步中，将大约n/2*d(x)数字的数量平方（并可能将该数字乘以较小的数字），然后通过将重复的数字相乘来完成算法平方x^(2^k)，如果2^k <= n < 2^(k+1)，与累加器。

让S(m)是平方数字的成本（可能与两个任意数字相乘m的成本相同，也可能不同）。然后平方需要大约M(m)m

S(2^(k-1)*d(x)) + S(2^(k-2)*d(x)) + S(2^(k-3)*d(x)) + ...

工作。因为S(m) >= m, 介于S(2^(k-1)*d(x))和之间2*S(2^(k-1)*d(x))。因此，平方的工作由最后一步控制。对于 ax^(2^s)与累加器的乘法，同样成立，最终的乘法占主导地位。最终的累加器几乎可以与重复平方一样大，因此通过重复平方提高x到n- 次方的总成本为

Θ(M(2^k*d(x)),

这是Θ(M(n*d(x)))。使用天真的乘法 -M(m) = O(m^2)然后你得到总成本O(n^2*d(x)^2). 使用更高级的乘法算法（Karatsuba、Toom-Cook、Schönhage-Strassen，...），您可以获得更低的复杂度，甚至略高于O(n*d(x)*log (n*d(x)) * log log (n*d(x))).

当通过与 相乘来迭代计算幂时x，n让M(m,k)表示将m-digit 数字与k-digit 数字相乘的成本。由于其中一个因素总是x，总成本是

M(d(x),d(x)) + M(d(x),2*d(x)) + M(d(x),3*d(x)) + ... + M(d(x),(n-1)*d(x))

用教科书算法加上成本M(m,k) = m*k，这个加起来n*(n-1)/2*d(x)^2，所以总成本又是Θ(n^2*d(x)^2)。但常数因子大于通过重复平方取幂的因子。

当您将长度差异很大的数字相乘时，就像在几次迭代之后发生的那样，您不能 - 据我所知 - 将成本降低到M(m,k)远低于Θ(m*k)- 如果m < k，将数字视为 1 位数字和 -r位数字（r*m <= k < (r+1)*m) 在 base中，如果足够大，您可以b^m使用更好的算法减少乘以“数字”的成本，但您不能减少因子。因此该算法的复杂度为，无法消除 的因素。mrO(n^2*M(d(x)))n^2

于 2012-08-05T19:27:31.473 回答
2

Wikipedia很好地概述了各种乘法算法的复杂度时间。

为了回答您的问题，假设将两个 m 位数字相乘（其复杂度为 O( m^2 ）的幼稚教科书方法和通过将数字乘以自身 n 次来提高幂的幼稚方法，您有n 次乘法，所以复杂度为 O( n * m^2 ) 或简单 O( nm^2 )

于 2012-08-05T15:40:24.147 回答
1

n^k 成本：

O((log(n))^k)

log(n) - n 的位表示

^k - 因为将两个 n 位数字相乘的简单算法成本为 O(n^2)

于 2012-08-05T16:29:05.097 回答