def subtraction_div(dividend: int, divisor: int) -> int:
if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
sign = -1
else:
sign = 1
dividend = abs(dividend)
divisor = abs(divisor)
quotient = 0
while dividend - divisor > 0:
quotient = 1
dividend -= divisor
if sign < 0:
quotient = - quotient
return quotient
我認為時間復雜度是 O(N)，而我的 CS 學位朋友向我列出了一些難以理解的公式并告訴我它是 O(2^N)。
uj5u.com熱心網友回復：
n是表示引數所需的位數，而不是最大可能的幅度（我們可以稱之為N）。N在 中呈指數增長n，而不是線性增長，并且減法的數量取決于N。（因此，減法的數量是輸入大小 QED 的指數。）
直觀地說，subtraction_div(100, 5)減法是 的 10 倍subtraction_div(10, 5)，即使輸入大小僅大 1 位。（二進制表示中的位數大致是比位數大 3 的常數因子，所以我們這里談時間復雜度時基本忽略了位數和位數的區別。）
您可以通過說引數以 base-1 位字串的形式提供來輕松地使演算法 O(n)，以便位大小和幅度相同，但時間復雜度僅在您將自己限制為有效編碼時才有用。除 1 以外的任何（正整數）基數都相當于在一個常數因子內；通常使用 2，因為生成的演算法描述更簡單。
uj5u.com熱心網友回復：
我們通常將復雜度作為n的函式來衡量，n中的位數與 log( N )成正比。
最壞的情況是N /1，在這種情況下有N個步驟。但是N =exp( n )，所以復雜度是O(N)=O(exp(n))。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/411530.html
標籤：