我解决了这个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
https://stackoverflow.com/questions/56264947
复制相似问题