algorithm - 大数相乘

在分析算法的时候，我发现我们通常假设乘法只接受一个计算机指令但当数字的大小（以比特数为单位）时，这种假设是不合适的。在最基本的乘法形式中，两个n位数相乘通常是o（n^2）。在这种情况下，计算X ^ n（x升到n的幂）的复杂性可能是什么（在位运算方面）？
用解释的方法，我的复杂性似乎是指数n（但不确定确切的数字）。

最佳答案

计算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相同，也可能不同）。方波则需要近似。

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

工作。因为M(m)，它介于m和S(m) >= m之间。所以平方的工作是由最后一步控制的。对于aS(2^(k-1)*d(x))与累加器的乘法，同样的情况下，最终乘法支配着工作。最终的累加器可以几乎和重复平方一样大，因此通过重复平方将2*S(2^(k-1)*d(x))提高到x^(2^s)第次功率的总成本是

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

即x。通过简单的乘法运算-n-你就得到了Θ(M(n*d(x)))的总成本使用更先进的乘法算法（Karatsuba，Toom Cook，SCH O-NHAGE Strassen，…），你得到的复杂度要低得多，略低于M(m) = O(m^2)。
当通过与O(n^2*d(x)^2)相乘迭代计算功率时，在O(n*d(x)*log (n*d(x)) * log log (n*d(x)))步骤中，让x表示将n位数与M(m,k)位数相乘的成本。因为其中一个因素总是m，所以总成本是

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

使用成本k的教科书算法，这将总计为x，因此总成本再次M(m,k) = m*k但常数因子比重复平方求幂的常数因子大。
当你用不同长度的数字相乘时，就像这里经过几次迭代后所发生的那样，据我所知，你不能将成本远远降低到低于n*(n-1)/2*d(x)^2的水平-如果Θ(n^2*d(x)^2)，则将数字视为1位数字和基数M(m,k)中的Θ(m*k)位数字（m < k），如果r足够大，但不能减少r*m <= k < (r+1)*m因子。因此，该算法的复杂度为cc，不能消除b^m的因子。

关于algorithm - 大数相乘，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11817683/