快速冪演算法
設計一個演算法計算\(x^n\)的值，
根據定義最常見也最能瞬間想到的是如下的演算法：
// 遞回寫法
public int pow1(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
return x * pow1(x, n - 1);
}
// 回圈寫法
public int pow2(int x, int n) {
int y = 1;
while (n) {
y *= x;
n--;
}
return y;
}
但上面的演算法的時間復雜度是\(O(n)\)
下面采用快速冪演算法來解決這個問題，
在解決它之前先來看一下原理：
\[x^{n}=x^{n-a}x^a \]所以我們可以對本身要求的\(x^n\)對半分來求，只求一半的數，然后乘以自己本身就可以達到\(x^n\)
但是會出現的情況就是，對半分的時候會出現小數的情況，所以一定要分奇數和偶數的情況，
如果n分半了之后是偶數，那就直接對半分，如果是奇數則在對半分之后還要乘以一個x，
所以可以有下面的規律：
f(x, n) = {
f(x, n/2)*f(x, n/2), // 當n為偶數
x*f(x, n/2)*f(x, n/2) // 當n為奇數
}
所以得出快速冪演算法1：
public int qPow1(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
if (n % 2 == 1) return x*f(x, n/2)*f(x, n/2);
return f(x, n/2)*f(x, n/2);
}
但是上面的演算法明顯沒有任何增進，因為f(x, n/2)要算兩次，那和之前的\(O(n)\)的演算法沒什么區別，所以使用一個中間變數去接受一下，就可以提高演算法效率，
public int qPow1(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
int t = f(x, n/2)
if (n % 2 == 1) return x * t * t;
return t * t;
}
上面的快速冪演算法還是比較好理解的，下面的快速冪演算法就比較的炫技了我覺得，但是也就那樣（原理還是上面的，只是不是對半分而已，而是根據進制數來分），
下面采用二進制數來分，
假設我們要計算的是\(x^{10}\)，那么10的二進制數是1010，所以有如下公式及變換：
\[x^{10}=x^{(10)_{10}}=x^{(1010)_2}=x^{1*2^3+0*2^2+1*2^1+0*2^0}=x^{8+2}=x^8x^2 \]即
\[x^{10}=x^8x^2 \]和上面第一種快速冪的演算法類似，只不過上一種采用的分法是：
\[x^{10}=x^5x^5 \]那么不管怎樣分，最后肯定會被分到1，因為\(x^0=1\)，其實上面的分法都隱藏了一個\(x^0\)，即：
\[x^{10}=x^8x^2x^0 \]所以狀態是怎么轉移的，即每一次迭代都是怎樣變化的，初始化\(t=x^{2^0}=x^1=x\)，那么下一代的變化是\(x^{2^1}\)，它是由\(x^{2^0*2}\)變化而來，因為采用的是二進制，所以指數部分要想從\(2^0\)變換到\(2^1\)就需要乘以一個2.那也就是說，\(x\)變到\(x^2\).那么迭代變化程序就是\(t=t*t\).
\(x^{2^0*2}=(x^{2^0})^2\)
所以得到第二種快速冪演算法代碼：
public int qPow2(int x, int n) {
int y = 1;
int t = x;
while (n > 0) {
switch (n % 2) {
case 1: y = y * t; // 這里不要寫break
case 0: t = t * t;
}
n = n / 2;
}
return y;
}
那么這個采用二進制的方法分，當然也有三進制的，四進制的，五進制的等等，十六進制就不要搞了，因為不是進制越高就越快，
通過我對上面的二進制寫法的快速冪就可以看出來我還會有其他進制的寫法，那么下面就來看一下三進制的寫法，然后四進制的就順其自然就明白了，
那么三進制的推導程序也是和二進制的推導程序是類似的，假設計算的是\(x^{10}\).
\[x^{10}=x^{(10)_{10}}=x^{(101)_3}=x^{1*3^2+0+3^1+1*3^0}=x^9x \]所以從二進制的分法和三進制的分法可以看出，不管怎么分都是可以合起來達到10.只要能達到10的說明采用什么進制分法都是可以的，但并不是說采用的進制越高就越好，
那么初始化\(t=x^{3^0}=x\)，那么下一代的變化是\(x^{3^1}\)，它是由\(x^{3^0*3}\)變化而來，因為采用的是三進制，所以指數部分要想從\(3^0\)變換到\(3^1\)就需要乘以一個3.那也就是說，\(x\)變到\(x^3\).那么迭代變化程序就是\(t=t*t*t\).
\(x^{3^0*3}=(x^{3^0})^3\)
對比一下二進制和三進制的區別，所以四進制往后的就不需要我一個個推導了吧，
直接得出演算法代碼：
public int qPow3(int x, int n) {
int y = 1;
int t = x;
while (n > 0) {
switch (n % 3) {
case 2: y = y * t; // 這里不要寫break
case 1: y = y * t; // 這里不要寫break
case 0: t = t * t * t;
}
n = n / 3;
}
return y;
}
直接得出四進制版本的代碼：
public int qPow4(int x, int n) {
int y = 1;
int t = x;
while (n > 0) {
switch (n % 4) {
case 3: y = y * t; // 這里不要寫break
case 2: y = y * t; // 這里不要寫break
case 1: y = y * t; // 這里不要寫break
case 0: t = t * t * t * t;
}
n = n / 4;
}
return y;
}
直接得出五進制版本的代碼：
public int qPow5(int x, int n) {
int y = 1;
int t = x;
while (n > 0) {
switch (n % 5) {
case 4: y = y * t; // 這里不要寫break
case 3: y = y * t; // 這里不要寫break
case 2: y = y * t; // 這里不要寫break
case 1: y = y * t; // 這里不要寫break
case 0: t = t * t * t * t;
}
n = n / 5;
}
return y;
}
以此類推，，，就不寫了，
可以去測驗一下：
public class Main {
public static void main(String[] args) {
System.out.println("計算2的10次方：");
int x = 2, n = 10;
Solution s = new Solution();
showMessage("pow1: ", s.pow1(x, n));
showMessage("pow2: ", s.pow2(x, n));
showMessage("qPow1: ", s.qPow1(x, n));
showMessage("qPow2: ", s.qPow2(x, n));
showMessage("qPow3: ", s.qPow3(x, n));
showMessage("qPow4: ", s.qPow4(x, n));
showMessage("qPow5: ", s.qPow5(x, n));
}
public static void showMessage(String str, int result) {
System.out.println("---------------------");
System.out.println(str + result);
System.out.println("---------------------");
}
}
class Solution {
public int pow1(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
return x * pow1(x, n - 1);
}
public int pow2(int x, int n) {
int y = 1;
while (n > 0) {
y = y * x;
n--;
}
return y;
}
public int qPow1(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
int t = qPow1(x, n / 2);
if (n % 2 == 1) return x * t * t;
return t * t;
}
public int qPow2(int x, int n) {
int y = 1;
int t = x;
while (n > 0) {
switch (n % 2) {
case 1: y = y * t; // 這里不要寫break
case 0: t = t * t;
}
n = n / 2;
}
return y;
}
public int qPow3(int x, int n) {
int y = 1;
int t = x;
while (n > 0) {
switch (n % 3) {
case 2: y = y * t; // 這里不要寫break
case 1: y = y * t; // 這里不要寫break
case 0: t = t * t * t;
}
n = n / 3;
}
return y;
}
public int qPow4(int x, int n) {
int y = 1;
int t = x;
while (n > 0) {
switch (n % 4) {
case 3: y = y * t; // 這里不要寫break
case 2: y = y * t; // 這里不要寫break
case 1: y = y * t; // 這里不要寫break
case 0: t = t * t * t * t;
}
n = n / 4;
}
return y;
}
public int qPow5(int x, int n) {
int y = 1;
int t = x;
while (n > 0) {
switch (n % 5) {
case 4: y = y * t; // 這里不要寫break
case 3: y = y * t; // 這里不要寫break
case 2: y = y * t; // 這里不要寫break
case 1: y = y * t; // 這里不要寫break
case 0: t = t * t * t * t * t;
}
n = n / 5;
}
return y;
}
}
終端輸出：
計算2的10次方：
---------------------
pow1: 1024
---------------------
---------------------
pow2: 1024
---------------------
---------------------
qPow1: 1024
---------------------
---------------------
qPow2: 1024
---------------------
---------------------
qPow3: 1024
---------------------
---------------------
qPow4: 1024
---------------------
---------------------
qPow5: 1024
---------------------
然后來分析一下它們的執行效率，
一般的\(O(n)\)就不說了，肯定是比\(O(log_2n)\)差的，主要是看是不是進制越高就越好？先給出答案，并不一定是，看著qPow5好像可以更快收到答案，但我們忘了看\(t=t*t*t*t*t\)這段代碼和它上面的那一坨，然后再放大一點看，如果我采用的是十進制的寫法，那會發現狀態轉移是\(t=t*t*t...（10個t）\)那和一般的pow有什么區別？所以，從這一點可以看出來并不是進制越高就越好，就好像是用\(x^8x^2\)和\(x^2x^8\)比效率一樣，都是一樣的嘛，如果外層回圈少了，那里面的乘法就多了，所以得找個平衡的點，那這個平衡的點一般也就是對半的時候（并不是所有情況都是），所以我們折騰了那么久又回到了二進制的版本，因為計算機底層是二進制，所以我們就采用二進制的版本，然后再采用代碼上的語法優化，這樣應該是更好一點，因為其它進制的版本可優化的點并不多，下面給出二進制優化的版本，
public int qPow2(int x, int n) {
int y = 1;
int t = x;
while (n > 0) {
if (n % 2 == 1) y *= t;
t *= t;
n >>= 1;
}
return y;
}
因為Java語法本身的原因在做位運算的時候不能像C/C++一樣可以用非零當作真，所以if (n % 2 == 1) y *= t;并不改變，但如果是C/C++的話可以采用下面的版本：
int qPow2(int x, int n) {
int y = 1;
while (n) {
if (n & 1) y *= t;
t *= t;
n >>= 1;
}
return y;
}
快速冪演算法就先到這里結束了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/549550.html
標籤：其他
下一篇：陣列的演算法