在m和n都屬于正數,并且m的n次方不超過LONG_MAX的情況下,如何求出m的n次方呢?一般都會想到用一個循環,如下
long result = 1;
for (int i = 0; i < n; i )
result * = m;
result即為所求,算法複雜度O(n)。這樣也能工作,但是當m和n變大時,效率會相當低下,如何優化呢?考慮2的4次方的情況,其實就是4個2相乘法;有沒有看出撒問題呢?是的,重複計算!前二個2相乘的結果可以直接用,後面兩個2的相乘不用再計算,即是
2X2X2X2 = 4X4
考慮2的5次方,即5個2相乘的情況,同樣的道理
2X2X2X2X2 = 4X4X2
所呈現出來的規律即是
m的n次方,在n為偶數時,可以變成 m的n/2次方的平方;在n為奇數時,則有n - 1為偶數,則變成m的(n-1)/2次方的平方再乘以m, 從n變成n/2,問題規模變小,中間計算結果可重複利用,可用遞歸解決,其算法複雜度變成O(logn)。具體代碼見下:
運行結果如下
,
更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!