目錄
快速冪
1.暴力
2.解決溢位問題
3.降低時間復雜度
4.代碼實作
5.課后習題
快速冪
快速冪一般用來解決 a^b % c 的問題，當然計算不模c的情況也行，
1.暴力
// 回傳結果a^b % c (c的范圍一般很小所以用了int)
public long pow(long a, long b, int c)
{
long res = 1;
for (long i = 0 ; i < b; i++)
{
res *= a;
}
return res % c;
}這種方法對于資料范圍小的情況還是可以的，但在特殊的情況下b的范圍很大，例如 0 < b < 10^18
缺陷：
-
計算中的res很容易超過long
-
時間復雜度高 O(N)
2.解決溢位問題
取模運算有個性質：(a * b) % p = ((a % p) * (b % p)) % p
下面我們來簡單證明下：
設：a = k1 * p + q1
b = k2 * p + q2
(a * b) = (...) * p + q1 * q2
即 (a * b) % p = (q1 * q2) % p （這里不知道q1 * q2是否大于p，所以還要取模一下）
又因為 a % p = (k1 * p + q1) % p = q1
b % p = (k2 * p + q2) % p = q2
所以 (a * b) % p = ((a % p) * (b % p)) % p
但這有什么用呢？
我們之前是( a * a * ...) % c，根據這個性質我們就可以邊乘邊對c取摸了，這樣不就解決了溢位問題了嗎
即：ans *= a; ans %= c;
但還有缺陷：
-
時間復雜度的問題沒有解決
3.降低時間復雜度
先看一下我們手算3^10是怎么算的?
3^10 = (3^2)^5 = 9^5 = 9 * 9^4 = 9 * (9^2)^2 = 9 * 81^2 ....
根據上面，我們很容易發現規律：
當指數是偶數時,讓指數除2,底數平方，
當指數是奇數的時候讓res乘一個底數，在讓指數除2，底數平方
這個演算法是時間復雜度是多少？ 每次讓指數 b /= 2，顯然是O(logN)
4.代碼實作
1.詳細版
public long quickPow(long a, long b, int c)
{
a %= c; // 防止一開始a過大
long res = 1; // 其實這里用int也行
while(b > 0)
{
if (b % 2 == 1) // 指數是奇數
{
res = (res * a) % c; // 邊乘邊摸
a = (a * a) % c;
b /= 2;
}
else // 指數是偶數
{
a = (a * a) % c;
b /= 2;
}
}
return res;
}2.簡潔版+位運算優化
public long quickPow(long a, long b, int c)
{
a %= c;
long res = 1;
while(b > 0)
{
if (b & 1 == 1) // b % 2 == 1
{
res = (res * a) % c;
}
a = (a * a) % c;
b >>= 1; // b /= 2;
}
return res;
}5.課后習題
leetcode ：
-
50.Pow(x, n)
-
372. 超級次方
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/375963.html
標籤：其他