python-3.x - 此除法函数的时间复杂度是多少(未使用除法或乘法运算符)？

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也是一样的我的算法会更快。同样越大dividend对于相同的 divisor我们的运行时间变慢了。

我的猜测是控制该算法运行时间的方程式基本上是 O(股息/除数)(呃，那是除法)的形式，其中有一些日志可以解释我乘以 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

在最坏的情况下，您的算法是 O(m^2)，其中 m 是结果中的位数。就输入而言，它将是 O(log(股息/除数) ^ 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 次迭代。