我有一個(gè)找到指數(shù)的函數(shù)，但我對(duì)函數(shù)的復(fù)雜性感到困惑。功能：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)我嘗試根據(jù)指數(shù)計(jì)算并繪制計(jì)算次數(shù)圖并得到以下結(jié)果： 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如您所見，計(jì)算次數(shù)在波動(dòng)，我認(rèn)為 Big-O 表示法不會(huì)是線性的或二次的。我認(rèn)為它會(huì)像一個(gè)多次多項(xiàng)式，其表示形式如下我是對(duì)的還是我對(duì) O(n) 表示法有錯(cuò)誤的想法？
2 回答
莫回?zé)o
TA貢獻(xiàn)1865條經(jīng)驗(yàn) 獲得超7個(gè)贊
這是一種眾所周知的算法，稱為快速求冪（有時(shí)是平方和乘法），其復(fù)雜度為O(log(n)). 維基百科有一整頁：https ://en.wikipedia.org/wiki/Exponentiation_by_squaring
但是如果你不知道這些信息，一種思考方式是重寫你的算法，這樣你就可以很容易地找到遞歸公式。主要困難是應(yīng)用于奇數(shù)和偶數(shù)的不同程序。訣竅是將它們組合在一起并僅進(jìn)行一次遞歸調(diào)用。
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
現(xiàn)在您可以看到，在算法的每一步，exponent都（大致）除以 2（這不再取決于其奇偶性），因此復(fù)雜度為log(n).
米琪卡哇伊
TA貢獻(xiàn)1998條經(jīng)驗(yàn) 獲得超6個(gè)贊
首先，您可以考慮最壞情況的算法。因此，如果T(n)是算法的時(shí)間，最壞的情況是T(n) = T(n-1) + c（c是一個(gè)常數(shù)，用于比較、求和、調(diào)用函數(shù)……）。因此，T(n) = O(n)。
此外，該聲明I think O(n) will not be linear or quadratic沒有意義。如果一個(gè)函數(shù)在 中O(n)，則意味著它至多是線性的。因此，它不可能是二次的。
現(xiàn)在您可以更仔細(xì)地檢查時(shí)間復(fù)雜度計(jì)算，并嘗試找到復(fù)雜度的嚴(yán)格界限。因?yàn)?，至少兩次連續(xù)遞歸，我們將得到一個(gè)偶數(shù)值exponent（因?yàn)槲覀冇?code>-1，如果exponent是奇數(shù)），因此，exponent到達(dá)1，最多2 log(n)計(jì)算（因?yàn)橹笖?shù)將至少除以 2在每 2 次連續(xù)遞歸中）。因此， 的緊界T(n)是O(log(n))。
添加回答
舉報(bào)
0/150
提交
取消