實(shí)現(xiàn)浮點(diǎn)類型的冪運(yùn)算，函數(shù)原型為:

double pow(double x, int n)

在求解這個(gè)問(wèn)題的時(shí)候是一個(gè)很掙扎的過(guò)程，因?yàn)樗皇菆?bào)錯(cuò)而是一直提示你超出時(shí)間，那么必須一次次的考慮怎樣降低時(shí)間復(fù)雜度。

首先最直接的思路是下面這樣的，就跟直觀的數(shù)學(xué)求解一樣。

double pow(double x, int n) {if(n==0)return 1.0;if(n<0)return 1.0/pow(x,-n);return x*pow(x,n-1); }

但是會(huì)提示你超出時(shí)間，這是可以理解的，因?yàn)闀r(shí)間復(fù)雜度是O(n)。對(duì)于較大的n這是不可接受的。

其次， 考慮到n個(gè)x相乘式子的對(duì)稱關(guān)系，可以對(duì)上述方法進(jìn)行改進(jìn)，從而得到一種時(shí)間復(fù)雜度為O(logn)的方法，遞歸關(guān)系可以表示為pow(x,n) = pow(x,n/2)*pow(x,n-n/2)。

double pow(double x, int n) {if(n==0)return 1.0;if(n<0)return 1.0/pow(x,-n);double half = pow(x,n>>1);if(n%2==0)return half*half;elsereturn half*half*x; }

這樣時(shí)間復(fù)雜度降低了一個(gè)數(shù)量級(jí)，但是仍然會(huì)超時(shí)。

最后，網(wǎng)上搜答案查到下面的解決方案，這根編程之美中求1的個(gè)數(shù)很類似。只不過(guò)加了一步數(shù)學(xué)冪轉(zhuǎn)化為乘法，即指數(shù)相加的過(guò)程。

描述如下：

Consider the binary representation of n. For example, if it is "10001011", then x^n = x^(1+2+8+128) = x^1 * x^2 * x^8 * x^128. Thus, we don't want to loop n times to calculate x^n. To speed up, we loop through each bit, if the i-th bit is 1, then we add x^(1 << i) to the result. Since (1 << i) is a power of 2, x^(1<<(i+1)) = square(x^(1<<i)). The loop executes for a maximum of log(n) times.

該方法通過(guò)掃描n的二進(jìn)制表示形式里不同位置上的1，來(lái)計(jì)算x的冪次。

double my_pow(double x, int n) {if(n==0)return 1.0;if(n<0)return 1.0 / pow(x,-n);double ans = 1.0 ;for(; n>0; x *= x, n>>=1){if(n&1>0)ans *= x;}return ans; }

這里有一個(gè)問(wèn)題就是當(dāng)n等于INT_MIN時(shí)，求絕對(duì)值之后會(huì)超出整數(shù)范圍，因?yàn)樨?fù)數(shù)是比正數(shù)多一個(gè)的。在這里作為一個(gè)邊界添加考慮即可。

if(n<0) { if(n==INT_MIN) return 1.0 / (pow(x,INT_MAX)*x); else return 1.0 / pow(x,-n); }

總結(jié)

以上是生活随笔為你收集整理的pow(x,y)函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。