这个除法函数的时间复杂度是多少(不使用除法或乘法运算符)？
我解决了这个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回答 2
Stack Overflow用户
发布于 2019-05-23 06:57:36
在最坏的情况下，您的算法是O(m^2)，其中m是结果中的位数。就输入而言，它将是O(log(被除数/除数)^ 2)。
要了解原因，请考虑您的循环的作用。设a=被除数，b=除数。循环减去b，2b，4b，8b，...只要它足够大，就从a开始，然后一次又一次地重复这个序列，直到a<b。
它可以等效地写成两个嵌套循环：
while dividend >= divisor:
Q = divisor
i = 0
while Q <= dividend:
dividend = dividend - Q
Q <<= 1
res += (1 << i)
i+=1对于外部循环的每次迭代，内部循环将执行较少的迭代，因为dividend较小。在最坏的情况下，对于外部循环的每次迭代，内循环只会少做一次迭代。在这种情况下，可以证明n =O(1+3+7+15+...+(1+3+7+15+...+))，但是内部循环迭代的总次数是O(n^2)，即结果的大小是二次的。
要将其改进为结果大小的线性，请首先计算所需的最大值Q和i。然后向后工作，从i中减去1，并在每次迭代中将Q右移。这保证了总迭代次数不超过2n次。
Stack Overflow用户
发布于 2019-05-23 06:34:20
最坏情况下的复杂性很容易发现。
每次迭代都会生成一部分结果，迭代次数等于商中的位数。
当为divider=1时，迭代次数为quotient=dividend，在这种情况下，迭代次数等于前导(最高有效) 1之后被除数中的比特数。当dividend=2^(n-1)+k时，迭代次数最大化，其中n是比特数，k是诸如1≤k<2^(n-1)之类的任何数字。这显然是最坏的情况。
在第一次迭代之后，被除数=被除数-除数(=被除数-1)和diviser=2^1
在迭代m之后，diviser=2^m和dividend=dividend-(1+2^1+..+2^(m-1))=dividend-(2^m-1)
当红利<0时，迭代停止。对于k>0，当dividend=2^(n-1)+k时，这发生在m=n上。
因此，最坏情况下的步数是n，复杂度与被除数的位数成线性关系。
https://stackoverflow.com/questions/56264947
复制相似问题