首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >这个除法函数的时间复杂度是多少(不使用除法或乘法运算符)?

这个除法函数的时间复杂度是多少(不使用除法或乘法运算符)?
EN

Stack Overflow用户
提问于 2019-05-23 04:59:56
回答 2查看 419关注 0票数 0

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

代码语言:javascript
复制
    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))。通常,对于算法,当每次迭代的输入除以2时,我们说它们是O(log(n))的,但在这里,我在每次迭代时将divisor乘以2 Q<<= 1,因此在每一步我都朝着解决方案迈出了更大的一步。显然,如果更大的divisordividend是相同的,我的算法会更快。同样,对于相同的divisordividend越大,我们的运行时间就越慢。

我猜这个算法的运行时间方程基本上是O(被除数/除数)(这就是除法)的形式,其中有一些对数,以说明我在每一步Q <<= 1中将Q乘以2……我不知道到底是什么。

编辑:

当我第一次发布这个问题时,我发布的算法是下面的一个,Alain Merigot的答案就是基于这个算法。上面的版本和上面的版本之间的区别是,我的红利永远不会低于0,从而导致更快的运行时间。

代码语言:javascript
复制
    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
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/56264947

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档