我有以下迭代平方的实现：
def power(a, b):
result = 1
while b > 0:
if b % 2 == 1:
result = mult(result, a)
a = mult(a, a)
b = b // 2
return result
该mult()方法将2个给定的数相乘，当一个是x位长，一个是y位长时，乘法运算的次数就是x*y+(x+y)运算，我在复杂度分析中需要考虑。
我试图找到一个O()结合做的一个函数arithemtic操作数的符号n和m时为n位长，b是M位长。我只需要考虑乘法线，并检查最坏的情况。
最坏的情况是 whenb是一个 m 位数字，其中所有m二进制数字都是 1，然后我有m循环的迭代，其中在每次迭代中 if 条件为真。
我不知道该怎么做的是我应该如何在计算中考虑a每次迭代都会增长的事实？我如何将它放入某种有限和，可能是我可以计算的几何级数？
谢谢
另外，我知道乘以 2 个 x 位和 y 位将导致 x*y+(x+y) 算术运算。
这不是（通常）正确的。处理器将在定义的周期数内将两个数字相乘，无论它们是否大。除非您正在处理大量数字，否则您应该考虑，关于渐近复杂度 (O)，将乘法视为一种运算，同样适用于加法、除法、...
在您的代码中，每次循环迭代都有四个操作中的三个（if b % 2 == 1，也许result = result*a，a = a*a，b = b // 2）。复杂度只取决于循环的迭代次数，即：log2(b)，因为b在每次迭代中被除以2。
对于巨大的数字，您有两个可能对渐近复杂度产生影响的操作：result = result*a和a = a*a。Cpython 使用Karatsuba 乘法，如果 n 是数字的位数，则为 O(n^log2(3))。
我将详细说明a*a。当你取一个数的平方时，你大致将位数乘以二。考虑 log2(b) 循环：a*a在第一次迭代中取 O(n^log2(3))，第二次取 O(2n^log2(3))，第二次取 O(4n^log2(3))，... .., O(bn)^log2(3)) 在最后。总和是 O((b*log2(b)*n)^log2(3))，如果我没记错的话！
对于a*a, ，如果您绑定到 O(x*y) 乘法算法，那么对于 log2(b) 循环，您有
那是 O(b^2 * n^2) = O(2^2m * n^2) 我想（现在没有时间检查！）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句