埃及乘法算法复杂度？

Question

我确实理解这个算法，但找不到一种方法来定义它的复杂性，我唯一知道的是它与第二个参数有关，因为如果它更小，步骤就会更少。你知道我该怎么做吗？对于任何给定的算法，是否有任何通用的方法来定义时间复杂度？

埃及乘法算法：

def egMul(x, y):
res = 0
while(y>0):
    if(y%2==0):
        x = x * 2
        y = y / 2
    else:
        y = y - 1
        res = res + x
return res

Answer 1

这段代码执行Theta(log(y))算术运算。通过考虑y的二进制表示，您可以看到它对出现在二进制表示中的每个1执行else分支，并执行if的第一个分支(将y除以2) floor(log_2(y))次。