埃及乘法算法复杂度？

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 分支，并且它执行 [=13= 的第一个分支]（将 y 除以 2）floor(log_2(y)) 次。