这种简单的减法除法复杂度是 O(n) 还是 O(2^n)？

Question

def subtraction_div(dividend: int, divisor: int) -> int:
    if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
        sign = -1
    else:
        sign = 1
    dividend = abs(dividend)
    divisor = abs(divisor)
    quotient = 0
    while dividend - divisor > 0:
        quotient += 1
        dividend -= divisor
    if sign < 0:
        quotient = - quotient
    return quotient

我认为时间复杂度是O(N)，而我的CS学位朋友列出了一些难以理解的公式给我并告诉我它是O(2^N)。

Answer 1

n 是表示参数所需的位数，而不是最大可能的数量级（我们可以称之为 N）。 N在n中呈指数增长，不是线性增长，减法的次数取决于N。（因此，减法次数是输入大小 QED 的指数。）

直观上，subtraction_div(100, 5) 的减法次数是 subtraction_div(10, 5) 的 10 倍，即使输入大小仅大 1 位。（二进制表示的位数大致是比位数大3的常数因子，所以这里讲时间复杂度的时候我们基本忽略了位数和位数的区别。）

您可以简单地使算法 O(n) 说参数是以 1 为基数的位字符串提供的，因此位大小和大小相同，但是时间复杂度只有在您将自己限制在高效编码时才有用。任何除1以外的（正整数）基都等价于一个常数因子内；通常使用2，因为得到的算法描述更简单。

Answer 2

我们通常将复杂度作为 n 的函数来衡量，N 中的位数与 log(N).

最坏的情况是N/1，这种情况下有N步。但是N=exp(n)，所以复杂度是O(N)=O(exp(n)).

这种简单的减法除法复杂度是 O(n) 还是 O(2^n)？

Is this naive division-by-subtraction complexity O(n) or O(2^n)?

python

algorithm

time-complexity