功耗的時間複雜度（）

Question

我實現了這個函數power()，它帶有兩個參數a和b並計算出^b。

typedef long long int LL; 

LL power(int a,int b) 
{ 
    int i = 1; 
    LL pow = 1; 
    for(; i <= b ; ++i) 
    pow *= a; 
    return pow; 
} 

給定：一個^{B以long long int範圍}下降。
問題：如何減少算法的時間複雜度？

Answer 1

按平方排列的指數。

一種非遞歸實現

LL power(int a, int b) 
{ 
    LL pow = 1; 
    while (b) 
    { 
     if (b & 1) 
     { 
      pow = pow * a; 
      --b; 
     } 
     a = a*a; 
     b = b/2; 
    } 
    return pow; 
} 

該算法需要日誌 b squarings和至多日誌 b乘法。

的運行時間爲O（log B）

---

Answer 2

使用Exponentiation by squaring

Answer 3

我建議：使用POW（）函數，如果你真的需要一個更快的功能（長雙）或者爲自己考慮作業。

任意精度：見GMP LIB http://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation

Answer 4

冪的平方不給在所有情況下乘法的數量降到最低。尋找「附加鏈」，「布勞爾鏈」，「漢森連鎖店」和「Scholz猜想」。

Answer 5

用正方形乘以指數。這就是說，如果我們需要a^b，我們檢查b是否均勻，如果b是偶數，我們找到(a^2)^(b/2)，否則我們找到a*((a^2)^(b/2))。這可能不是最好的算法，但它比線性算法更好。

int Power(int a, int b) 
{ 
    if (b>0) 
    { 
     if (b==0) 
      return 1; 
     if (a==0) 
      return 0; 
     if (b%2==0) { 
      return Power(a*a, b/2); 
     } 
     else if (b%2==1) 
     { 
     return a*Power(a*a,b/2); 
     } 
    } 
    return 0; 
} 

Answer 6

下面是遞歸實現的Java代碼 爲2到n的功率與O（log n）的使用Exponentiation by squaring

int ans=1; 
public int myTwoPower(int n){ 
    if(n<=0) 
     return 1; 

    if(n%2 !=0){    
     return myTwoPower(n-1)*2; 
    } 
    else{ 
     ans = myTwoPower(n/2); 
     return ans * ans; 
    } 
}