整數(shù)的冪計算

github: https://github.com/Sean16SYSU/Algorithms4N

算法1： 一般來說的常見的計算$x^n$的方式，就是逐步乘上x，這樣一共需要$O(n)次$的乘法
算法2： 但如果$x^4$的話，其實我們只需要計算一次$x^2$，再用兩個$x^2$相乘就好了。這樣的話，算法復(fù)雜度就被降低到了$O(logn)$ 。如果不是偶數(shù)的話，也可以通過提取出一個偶數(shù)來得到對應(yīng)的結(jié)果。用遞歸的方式很容易就解決上面描述的算法。

算法3： 但是，指數(shù)部分的是可以很容易用二進(jìn)制表示出來的。這樣我們就通過獲取對應(yīng)的二進(jìn)制位就來實現(xiàn)遞推實現(xiàn)(且由于不存在遞歸調(diào)用，一定程度上可以提高速度)。

算法1:

#include <iostream> using namespace std;double power(double x, unsigned int n) {double y = 1;for (int i = 0; i < n; ++i) { y *= x; }return y; }int main() {double x;unsigned int n;cin >> x >> n;cout << power(x, n) << endl;system("pause"); }

算法2

#include <iostream> using namespace std;double power(double x, unsigned int n) {double y;if (n == 0)y = 1;else{y = power(x, n / 2);y = y * y;if (n % 2 == 1)y *= x;}return y; }int main() {double x;unsigned int n;cin >> x >> n;cout << power(x, n) << endl;system("pause"); }

算法3

#include <iostream> using namespace std;double power(double x, unsigned int n) {double y = 1;while (n != 0){if (n % 2)y *= x;x *= x;n /= 2;}return y; }int main() {double x;unsigned int n;cin >> x >> n;cout << power(x, n) << endl;system("pause"); }

總結(jié)

以上是生活随笔為你收集整理的整数的幂计算（三种方法）最快O(logn)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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