这个除法函数的时间复杂度是多少(不使用除法或乘法运算符)？
这个除法函数的时间复杂度是多少(不使用除法或乘法运算符)？
提问于 2019-05-23 04:59:56
我解决了这个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))。通常，对于算法，当每次迭代的输入除以2时，我们说它们是O(log(n))的，但在这里，我在每次迭代时将divisor乘以2 Q<<= 1，因此在每一步我都朝着解决方案迈出了更大的一步。显然，如果更大的divisor的dividend是相同的，我的算法会更快。同样，对于相同的divisor，dividend越大，我们的运行时间就越慢。
我猜这个算法的运行时间方程基本上是O(被除数/除数)(这就是除法)的形式，其中有一些对数，以说明我在每一步Q <<= 1中将Q乘以2……我不知道到底是什么。
编辑：
当我第一次发布这个问题时，我发布的算法是下面的一个，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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56264947
复制相关文章
相似问题
腾讯云开发者
