此除法函数的时间复杂度是多少（未使用除法或乘法运算符）？

Question

我解决了这个 leetcode 问题 https://leetcode.com/problems/divide-two-integers/。目标是在不使用乘法或除法运算符的情况下获得 dividend 除以 divisor 的商。这是我的解决方案：

    def divide(dividend, divisor):     
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        sign = [1,-1][(dividend < 0) != (divisor < 0)]
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        i = 0
        Q = divisor
        while dividend >= divisor:
            dividend = dividend - Q
            Q <<= 1
            res += (1 << i)
            i+=1
            if dividend < Q:
                Q = divisor
                i = 0

        if sign == -1:
            res = -res

        if res < -2**31 or res > 2**31 -1:
            return 2**31 - 1

        return res

所以我无法分析这个解决方案的时间复杂度。我知道应该是O(log(something))。通常对于算法，我们说它们是 O(log(n)) 当输入在每次迭代中除以 2 但在这里我在每次迭代中将 divisor 乘以 2 Q<<= 1 所以在每一步我都采取更大的迈向解决方案。显然，如果 dividend 对于更大的 divisor 相同，我的算法会更快。同样，对于相同的 divisor，dividend 越大，我们得到的运行时间就越慢。

我的猜测是控制该算法运行时间的方程基本上是 O(dividend/divisor) 的形式（呃，那是除法），其中有一些日志来解释我乘以 Q 每一步增加 2 Q <<= 1...我不知道到底是什么。

编辑：

当我第一次发布问题时，我发布的算法是下面的算法，Alain Merigot 的答案是基于该算法的。顶部版本和上面那个版本之间的区别是我的股息从未低于 0，从而导致更快的运行时间。

    def divide(dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        sign = [1,-1][(dividend < 0) != (divisor < 0)]
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        i = 0
        tmp_divisor = divisor
        while dividend >= divisor:
            old_dividend, old_res = dividend, res
            dividend = dividend - tmp_divisor
            tmp_divisor <<= 1
            res += (1 << i)
            i+=1
            if dividend < 0:
                dividend = old_dividend
                res = old_res
                tmp_divisor >>= 2
                i -= 2

        if sign == -1:
            res = -res

        if res < -2**31 or res > 2**31 -1:
            return 2**31 - 1

        return res

Answer 1

最坏情况下的复杂度很容易找到。

每次迭代生成结果的一位，迭代次数等于商的位数。

当除数=1时，商=被除数，在这种情况下，迭代次数等于前导（最高有效）1之后被除数中的位数。当被除数=2^(n- 1)+k，其中 n 是位数，k 是任何数字，例如 1≤k<2^(n-1)。这显然是最坏的情况。

第一次迭代后，dividend=dividend-diviser(=dividend-1) and diviser=2^1

经过m次迭代后，diviser=2^m and dividend=dividend-(1+2^1+..+2^(m-1))=dividend-(2^m-1)

当股息 <0 时迭代停止。由于 dividend=2^(n-1)+k，k>0，这发生在 m=n.

因此，最坏情况下的步骤数为n，复杂度与被除数的位数成线性关系。

Answer 2

您的算法在 worst-case 中为 O(m^2)，其中 m 是结果中的位数。就输入而言，它将是 O(log(dividend/divisor) ^ 2).

要了解原因，请考虑您的循环的作用。让a=股息，b=除数。循环从 a 中减去 b, 2b, 4b, 8b, ... 只要它足够大，然后一次又一次地重复这个序列直到 a<b.

可以等价地写成两个嵌套循环：

while dividend >= divisor:
    Q = divisor
    i = 0
    while Q <= dividend:
        dividend = dividend - Q
        Q <<= 1
        res += (1 << i)
        i+=1

对于外循环的每次迭代，内循环将执行较少的迭代，因为dividend更小。在最坏的情况下，内循环只会比外循环的每次迭代少执行一次迭代。当某些 n 的结果为 1+3+7+15+...+(2^n-1) 时，就会发生这种情况。在这种情况下，可以证明 n = O(log(result))，但是内循环迭代的总数是 O(n^2)，即结果大小的二次方。

为了改进结果大小的线性，首先计算 Q 和 i 所需的最大值。然后向后工作，从 i 中减去 1 并在每次迭代时将 Q 右移。这保证总共不超过 2n 次迭代。

此除法函数的时间复杂度是多少（未使用除法或乘法运算符）？

What is the time complexity of this division function (no divide or multiply operators used)?

algorithm

bit-shift

division

bitwise-operators

python-3.x