我有一個找到指數的函數，但我對函數的復雜性感到困惑。功能：def expo(number, exponent): if exponent == 0: return 1 elif exponent % 2 == 0: val = expo(number, exponent / 2) return val * val else: return number * expo(number, exponent - 1)我嘗試根據指數計算并繪制計算次數圖并得到以下結果： Graph: Exponent : Calculations:1 : 2, 2 : 3, 3 : 4, 4 : 4, 5 : 5, 6 : 5, 7 : 6, 8 : 5, 9 : 6, 10 : 6, 11 : 7, 12 : 6, 13 : 7, 14 : 7, 15 : 8, 16 : 6, 17 : 7, 18 : 7, 19 : 8, 20 : 7, 21 : 8, 22 : 8, 23 : 9, 24 : 7, 25 : 8, 26 : 8, 27 : 9, 28 : 8, 29 : 9, 30 : 9如您所見，計算次數在波動，我認為 Big-O 表示法不會是線性的或二次的。我認為它會像一個多次多項式，其表示形式如下我是對的還是我對 O(n) 表示法有錯誤的想法？
2 回答
莫回無
TA貢獻1865條經驗 獲得超7個贊
這是一種眾所周知的算法，稱為快速求冪（有時是平方和乘法），其復雜度為O(log(n)). 維基百科有一整頁：https ://en.wikipedia.org/wiki/Exponentiation_by_squaring
但是如果你不知道這些信息，一種思考方式是重寫你的算法，這樣你就可以很容易地找到遞歸公式。主要困難是應用于奇數和偶數的不同程序。訣竅是將它們組合在一起并僅進行一次遞歸調用。
def expo(number, exponent):
if exponent == 0:
return 1
elif exponent % 2 == 0:
val = expo(number, exponent / 2)
return val * val
else:
return number * expo(number, exponent - 1) # exponent - 1 is even !
可以改寫
def expo(number, exponent):
if exponent == 0:
return 1
elif exponent % 2 == 0:
val = expo(number, exponent / 2)
return val * val
else:
return number * expo(number, (exponent - 1) / 2) ** 2
現在您可以看到，在算法的每一步，exponent都（大致）除以 2（這不再取決于其奇偶性），因此復雜度為log(n).
米琪卡哇伊
TA貢獻1998條經驗 獲得超6個贊
首先，您可以考慮最壞情況的算法。因此，如果T(n)是算法的時間，最壞的情況是T(n) = T(n-1) + c（c是一個常數，用于比較、求和、調用函數……）。因此，T(n) = O(n)。
此外，該聲明I think O(n) will not be linear or quadratic沒有意義。如果一個函數在 中O(n)，則意味著它至多是線性的。因此，它不可能是二次的。
現在您可以更仔細地檢查時間復雜度計算，并嘗試找到復雜度的嚴格界限。因為，至少兩次連續遞歸，我們將得到一個偶數值exponent（因為我們有-1，如果exponent是奇數），因此，exponent到達1，最多2 log(n)計算（因為指數將至少除以 2在每 2 次連續遞歸中）。因此， 的緊界T(n)是O(log(n))。
添加回答
舉報
0/150
提交
取消