在分析算法时,我看到我们通常假设乘法采用单条计算机指令。但是当数字的大小(就位数而言)时,这个假设就不合适了。在最基本的乘法形式中,将两个 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
-digit 数字(可能与乘以两个任意 M(m)
-digit 数字的成本 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))
.所以平方的工作由最后一步主导。对于 x^(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
的成本- 带有 k
的数字-数字。由于其中一个因素始终是 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
, 将数字视为一位数字和 r
基数 r*m <= k < (r+1)*m
中的数字 ( b^m
) ,如果m
,您可以使用更好的算法降低乘以“数字”的成本。足够大,但不能减少 r
因素。所以这个算法的复杂度是O(n^2*M(d(x)))
, n^2
的因数无法消除。
关于algorithm - 大数乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11817683/