[[416359]]

本文轉(zhuǎn)載自微信公眾號(hào)「bigsai」，作者大賽。轉(zhuǎn)載本文請(qǐng)聯(lián)系bigsai公眾號(hào)。

前言

大家好，我是bigsai，之前有個(gè)小老弟問(wèn)到一個(gè)劍指offer一道相關(guān)快速冪的題，這里梳理一下講一下快速冪!

快速冪是什么?

顧名思義，快速冪就是快速算底數(shù)的n次冪。你可能疑問(wèn)，求n次冪算n次疊乘不就行了?當(dāng)n巨大無(wú)比時(shí)候，如果需要末尾有效尾數(shù)值等信息這個(gè)可能超出計(jì)算機(jī)運(yùn)算范圍。

有多快?

快速冪時(shí)間復(fù)雜度為 O(log?n)， 與樸素的O(n)相比效率有了極大的提高(int 范圍10位長(zhǎng)度數(shù)字32次之內(nèi)就能搞定，long 范圍20位長(zhǎng)度數(shù)字64次之內(nèi)也能搞定，你看有多快)。

用的多么?

快速冪屬于數(shù)論的范疇，本是ACM經(jīng)典算法，但現(xiàn)在各廠對(duì)算法的要求越來(lái)越高，并且快速冪適用場(chǎng)景也比較低多并且相比樸素方法有了非常大的提高，所以掌握快速冪算法已經(jīng)是一名更合格的工程師必備要求!

下面來(lái)詳細(xì)看看快速冪算法吧!

快速冪介紹

先看個(gè)問(wèn)題再說(shuō)：

初探

首先問(wèn)你一個(gè)問(wèn)題，如果讓你求 (2^10)%1000你可能會(huì)這樣寫：

int va=1; 
for(int i=0;i<10;i++) 
{ 
  va*=2; 
} 
System.out.println(va%10000); 

熟悉的1024沒(méi)問(wèn)題，總共計(jì)算了10次。但是如果讓你算 (2^50)%10000呢?

你可能會(huì)竊喜，小樣，這就想難住我?我知道int只有32位，50位超出范圍會(huì)帶來(lái)數(shù)值越界的異常，我這次可以用long，long有64位呢!

long va=1; 
for(int i=0;i<50;i++) 
{ 
  va*=2; 
} 
System.out.println(va); 
System.out.println(va%10000); 

計(jì)算50次出了結(jié)果正當(dāng)你暗暗私喜的時(shí)候又來(lái)了一個(gè)要命的問(wèn)題：讓你算 (2^1e10)%10000 且不許你用Java大數(shù)類，你為此苦惱不知所措。這時(shí)bigsai小哥哥讓你百度下取模運(yùn)算，然后你恍然大悟，在紙上寫了幾個(gè)公式：

(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） 

你還算聰明一眼發(fā)現(xiàn)其中的規(guī)律：

(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 

憑借這個(gè)遞推你明白：每次相乘都取模。機(jī)智的你pia pia寫下以下代碼，卻發(fā)現(xiàn)另一個(gè)問(wèn)題：怎么跑不出來(lái)?

咱們打工人需要對(duì)計(jì)算機(jī)運(yùn)行速度和數(shù)值有一個(gè)大致的概念。循環(huán)體中不同操作占用時(shí)間不同，所以當(dāng)你的程序循環(huán)次數(shù)到達(dá)1e6或1e7的時(shí)候就需要非常非常小心了。如果循環(huán)體邏輯或者運(yùn)算較多可能非常非常慢。

快速冪探索

機(jī)智的小女孩不甘失敗，開始研究其數(shù)的規(guī)律，將這個(gè)公式寫在手上、膀子上、小紙條上。吃飯睡覺(jué)都在看：

然后小女孩突然發(fā)現(xiàn)其中的奧秘，n次冪可以拆分成一個(gè)平方計(jì)算后就剩余n/2的次冪了：

現(xiàn)在你已經(jīng)明白了快速冪是怎么回事，但小女孩可能有點(diǎn)上頭，還是給我講了很多內(nèi)容：

快速冪實(shí)現(xiàn)

至于快速冪已經(jīng)懂了，我們?cè)撛趺磳?shí)現(xiàn)這個(gè)算法呢?

說(shuō)的不錯(cuò)，確實(shí)有遞歸和非遞歸的實(shí)現(xiàn)方式，但是遞歸使用的更多一些。在實(shí)現(xiàn)的時(shí)候，注意一下奇偶性、停止條件就可以了，奇數(shù)問(wèn)題可以轉(zhuǎn)換為偶數(shù)問(wèn)題：

2*2*2*2*2=2 * (2*2*2*2) 奇數(shù)問(wèn)題可以轉(zhuǎn)化為偶數(shù)問(wèn)題。 

這里，遞歸的解法如下：

long c=10000007; 
public  long divide(long a, long b) { 
        if (b == 0) 
            return 1; 
        else if (b % 2 == 0) //偶數(shù)情況 
            return divide((a % c) * (a % c), b / 2) % c; 
    else//奇數(shù)情況 
            return a % c * divide((a % c) * (a % c), (b - 1) / 2) % c; 
    } 

非遞歸實(shí)現(xiàn)也不難，控制好循環(huán)條件即可：

//求 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; 
} 

對(duì)于非遞歸你可能有點(diǎn)模糊為啥偶數(shù)情況不給res賦值。這里有兩點(diǎn)：

• 為奇數(shù)的情況res僅僅是收集相乘那個(gè)時(shí)候落單的a
• 最終b均會(huì)降到1，a最終都會(huì)和res相乘，不用擔(dān)心會(huì)漏掉
• 理想狀態(tài)一直是偶數(shù)情況，那最后直接獲得a取模的值即可。

如果還是不懂，可以用這個(gè)圖來(lái)解釋一下：

矩陣快速冪

你以為這就結(jié)束了?雖然快速冪主要內(nèi)容就是以上內(nèi)容，但是總有很多牛人能夠發(fā)現(xiàn)很有趣的規(guī)律—矩陣快速冪。如果你沒(méi)聽過(guò)的話建議仔細(xì)看看了解一下。

大家都知道斐波那契數(shù)列：的規(guī)則：

前幾個(gè)斐波那契的數(shù)列為：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

斐波那契從遞推式就可以看出是指數(shù)級(jí)別的增長(zhǎng)，所以稍微多幾個(gè)數(shù)字就是爆炸式增長(zhǎng)，所以很多時(shí)候也會(huì)要求最后幾位的結(jié)果。有了前面模運(yùn)算公式溢出就不成問(wèn)題，但n如果非常非常大怎么快速計(jì)算就成了一個(gè)新的問(wèn)題。

我們看下面一組公式：

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

如果拿f(n)和f(n-1)放到一個(gè)矩陣中(一行兩列)：[f(n+1),f(n)] 能否找到和[f(n),f(n-1)]之間的什么規(guī)律呢?

答案是存在規(guī)律的，看上面的公式知道：

[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]   
 
=·······           

所以現(xiàn)在你可以知道它的規(guī)律了吧，這樣一直迭代到f(2),f(1)剛好都為1，所以這個(gè)斐波那契的計(jì)算為：

而這個(gè)矩陣有很多次冪，就可以使用快速冪啦，原理一致，你只需要寫一個(gè)矩陣乘法就可以啦,下面提供一個(gè)矩陣快速冪求斐波那契第n項(xiàng)的后三位數(shù)的模板，可以拿這個(gè)去試一試poj3070的題目啦。

public int Fibonacci(int n) 
    { 
        n--;//矩陣為兩項(xiàng) 
        int a[][]= {{1,1},{1,0}};//進(jìn)行快速冪的矩陣 
        int b[][]={{1,0},{0,1}};//存儲(chǔ)漏單奇數(shù)、結(jié)果的矩陣，初始為單位矩陣 
        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;//確定每一排有幾個(gè) 
        int c[][]=new int [x][y]; 
        for(int i=0;i<x;i++) 
            for(int j=0;j<y;j++) 
            { 
                //需要確定每一個(gè)元素 
                //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數(shù)值的整數(shù)次方)上就有一道快速冪的問(wèn)題，我們用學(xué)的東西鞏固一下：

實(shí)現(xiàn) pow(x n) ，即計(jì)算 x 的 n 次冪函數(shù)(即，x^n)。不得使用庫(kù)函數(shù)，同時(shí)不需要考慮大數(shù)問(wèn)題。

這個(gè)簡(jiǎn)單題需要考慮一些特殊情況：

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

在實(shí)現(xiàn)上首先判斷n正負(fù)，將負(fù)次冪轉(zhuǎn)成正次冪。如果中轉(zhuǎn)一層long處理就不會(huì)出現(xiàn)這些問(wèn)題。

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會(huì)溢出 
        } 
        if(n%2==0) 
            return myPow(x*x,n/2); 
        else 
            return x*myPow(x*x,(n-1)/2); 
    } 
} 

結(jié)語(yǔ)

這篇到這里就肝完啦，其實(shí)快速冪的內(nèi)容還不止這么多，尤其是矩陣快速冪，會(huì)有著各種巧妙的變形，不過(guò)跟數(shù)學(xué)有一些關(guān)系，在力扣上比較少，但是在其他OJ上快速冪題目還是很多的可以自行找一下刷一刷。

是不是看完又get一個(gè)小知識(shí)!