一文徹底搞懂快速幂(原理、實現、矩陣快速幂)

Big sai 2021-08-15 15:34:52 阅读数:196

本文一共[544]字,预计阅读时长:1分钟~
一文 搞懂 快速 原理 快速

前言

大家好,我是bigsai,之前有個小老弟問到一個劍指offer一道相關快速幂的題,這裏梳理一下講一下快速幂!

快速幂是什麼?

顧名思義,快速幂就是快速算底數的n次幂。你可能疑問,求n次幂算n次疊乘不就行了?當n巨大無比時候,如果需要末尾有效尾數值等信息這個可能超出計算機運算範圍。

有多快?

快速幂時間複雜度為 O(log₂n), 與樸素的O(n)相比效率有了極大的提高(int 範圍10比特長度數字32次之內就能搞定,long 範圍20比特長度數字64次之內也能搞定,你看有多快)。

用的多麼?

快速幂屬於數論的範疇,本是ACM經典算法,但現在各廠對算法的要求越來越高,並且快速幂適用場景也比較低多並且相比樸素方法有了非常大的提高,所以掌握快速幂算法已經是一名更合格的工程師必備要求!

下面來詳細看看快速幂算法吧!

快速幂介紹

先看個問題再說:

初探

首先問你一個問題,如果讓你求 (2^10)%1000你可能會這樣寫:

int va=1;
for(int i=0;i<10;i++)
{

va*=2;
}
System.out.println(va%10000);

熟悉的1024沒問題,總共計算了10次。但是如果讓你算 (2^50)%10000呢?

你可能會竊喜,小樣,這就想難住我?我知道int只有32比特,50比特超出範圍會帶來數值越界的异常,我這次可以用long,long有64比特呢!

long va=1;
for(int i=0;i<50;i++)
{

va*=2;
}
System.out.println(va);
System.out.println(va%10000);

計算50次出了結果正當你暗暗私喜的時候又來了一個要命的問題:讓你算 (2^1e10)%10000 且不許你用Java大數類,你為此苦惱不知所措。這時bigsai小哥哥讓你百度下取模運算,然後你恍然大悟,在紙上寫了幾個公式:

(a + b) % p = (a % p + b % p) % p (1(a - b) % p = (a % p - b % p ) % p (2(a * b) % p = (a % p * b % p) % p (3)
a ^ b % p = ((a % p)^b) % p (4

你還算聰明一眼發現其中的規律:

(a * b) % p = (a % p * b % p) % p (3)
(2*2*2···*2) %1e10=[2*(2*2···*2)]%1e5=(2%1e5)*(2*2···*2%le5)%1e5

憑借這個遞推你明白:每次相乘都取模。機智的你pia pia寫下以下代碼,卻發現另一個問題:怎麼跑不出來?

image-20201028160221192

咱們打工人需要對計算機運行速度和數值有一個大致的概念。循環體中不同操作占用時間不同,所以當你的程序循環次數到達1e6或1e7的時候就需要非常非常小心了。如果循環體邏輯或者運算較多可能非常非常慢。

image-20201028163737620

快速幂探索

機智的你不甘失敗,開始研究其數的規律,將這個公式寫在手上、膀子上、小紙條上。吃飯睡覺都在看:

image-20201028171029641

然後你突然發現其中的奧秘,n次幂可以拆分成一個平方計算後就剩餘n/2的次幂了:

image-20201028174250098

現在你已經明白了快速幂是怎麼回事,但你可能有點上頭,還是給我講了很多內容:

image-20201028180224832

快速幂實現

至於快速幂已經懂了,我們該怎麼實現這個算法呢?

image-20201028185101226

說的不錯,確實有遞歸和非遞歸的實現方式,但是遞歸使用的更多一些。在實現的時候,注意一下奇偶性、停止條件就可以了,奇數問題可以轉換為偶數問題:

2*2*2*2*2=2 * (2*2*2*2) 奇數問題可以轉化為偶數問題。

這裏,遞歸的解法如下

long c=10000007;
public long divide(long a, long b) {

if (b == 0)
return 1;
else if (b % 2 == 0) //偶數情况
return divide((a % c) * (a % c), b / 2) % c;
else//奇數情况
return a % c * divide((a % c) * (a % c), (b - 1) / 2) % c;
}

非遞歸實現也不難,控制好循環條件即可:

//求 a^b%1000000007
long c = 1000000007;
public long divide(long a, long b) {

a %= c;
long res = 1;
for (; b != 0; b /= 2) {

if (b % 2 == 1)
res = (res * a) % c;
a = (a * a) % c;
}
return res;
}

對於非遞歸你可能有點模糊為啥偶數情况不給res賦值。這裏有兩點:

  • 為奇數的情况res僅僅是收集相乘那個時候落單的a
  • 最終b均會降到1,a最終都會和res相乘,不用擔心會漏掉
  • 理想狀態一直是偶數情况,那最後直接獲得a取模的值即可。

如果還是不懂,可以用這個圖來解釋一下:

image-20201028192842778

矩陣快速幂

你以為這就結束了?雖然快速幂主要內容就是以上內容,但是總有很多牛人能够發現很有趣的規律—矩陣快速幂。如果你沒聽過的話建議仔細看看了解一下。

大家都知道斐波那契數列: 的規則:

image-20201028193231170

前幾個斐波那契的數列為:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

斐波那契從遞推式就可以看出是指數級別的增長,所以稍微多幾個數字就是爆炸式增長,所以很多時候也會要求最後幾比特的結果。有了前面模運算公式溢出就不成問題,但n如果非常非常大怎麼快速計算就成了一個新的問題。

我們看下面一組公式:

f(n+1) = f(n) + f(n-1)
f(n) = f(n)

如果那f(n)和f(n-1)放到一個矩陣中(一行兩列):[f(n+1),f(n)] 能否找到和[f(n),f(n-1)]之間的什麼規律呢?

答案是存在規律的,看上面的公式知道

[f(n+1),f(n)]
=[f(n)+f(n-1),f(n)]
[1 1]
=[f(n),f(n-1)] *
[1 0]
[1 1] [1 1]
=[f(n-1),f(n-2)]* *
[1 0] [1 1]
=·······

所以現在你可以知道它的規律了吧,這樣一直迭代到f(2),f(1)剛好都為1,所以這個斐波那契的計算為:

image-20201028195631635

而這個矩陣有很多次幂,就可以使用快速幂啦,原理一致,你只需要寫一個矩陣乘法就可以啦,下面提供一個矩陣快速幂求斐波那契第n項的後三比特數的模板,可以拿這個去試一試poj3070的題目啦。

public int Fibonacci(int n)
{

n--;//矩陣為兩項
int a[][]= {
{
1,1},{
1,0}};//進行快速幂的矩陣
int b[][]={
{
1,0},{
0,1}};//存儲漏單奇數、結果的矩陣,初始為單比特矩陣
int time=0;
while(n>0)
{

if(n%2==1)
{

b=matrixMultiplication(a, b);
}
a=matrixMultiplication(a, a);
n/=2;
}
return b[0][0];
}
public int [][]matrixMultiplication(int a[][],int b[][]){
//
int x=a.length;//a[0].length=b.length 為滿足條件
int y=b[0].length;//確定每一排有幾個
int c[][]=new int [x][y];
for(int i=0;i<x;i++)
for(int j=0;j<y;j++)
{

//需要確定每一個元素
//c[i][j];
for(int t=0;t<b.length;t++)
{

c[i][j]+=(a[i][t]%10000)*(b[t][j]%10000);
c[i][j]%=10000;
}
}
return c;
}

小試牛刀

在力扣(劍指offer16數值的整數次方)上就有一道快速幂的問題,我們用學的東西鞏固一下:

實現 pow(x n) ,即計算 x 的 n 次幂函數(即,x^n)。不得使用庫函數,同時不需要考慮大數問題。

這個簡單題需要考慮一些特殊情况:

  • n正負性
  • 邊界(int最大和最小)

在實現上首先判斷n正負,將負次幂轉成正次幂。如果中轉一層long處理就不會出現這些問題。

class Solution {

public double myPow(double x, int n) {

if(n==0)
return 1;
if(n==1)
return x;
if(n<0){

return (1/x)*myPow((1/x),-(n+1));//不要-n-1會溢出
}
if(n%2==0)
return myPow(x*x,n/2);
else
return x*myPow(x*x,(n-1)/2);
}
}

結語

這篇到這裏就肝完啦,其實快速幂的內容還不止這麼多,尤其是矩陣快速幂,會有著各種巧妙的變形,不過跟數學有一些關系,在力扣上比較少,但是在其他OJ上快速幂題目還是很多的可以自行找一下刷一刷。

image-20201028210842709

關於作者:bigsai,在讀研一,手握騰訊、字節實習offer,藍橋杯國一選手,專注於數據結構與算法、Java領域的知識分享,喜歡用圖將複雜內容簡單化,有同名公眾號**【bigsai】,堅持輸出幹貨,如果有學習、實習、考研、選擇**等問題歡迎交流!

版权声明:本文为[Big sai]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815153425678d.html