权力的时间复杂度（）

我实现了这个函数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; } 

给定：a ^b落在long long int的范围内。
问题：如何降低算法的时间复杂度？

Answer 1

Squaring的指数。

非递归实现

 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; } 

该算法需要log ₂ b方形和最多log ₂ b乘法。

运行时间为O（log b）

---

Answer 2

通过平方使用指数

Answer 3

在所有情况下，通过平方的指数并不能给出最小的乘法次数。 寻找“附加链”，“Brauer链”，“Hansen链”和“Scholz猜想”。

Answer 4

我建议：使用pow（）函数，如果你真的需要更快的function（长双）或考虑你自己的功课。

对于任意精度：请参阅GMP lib http://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation

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

下面是使用Exponentiation进行平方的递归实现2代码到n的幂，具有O（log n）复杂度

 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; } }