快捷導(dǎo)航

Java中如何編寫一個數(shù)的n次方（冪運算）?

更新時間：2024年07月13日 15:14:30 作者：拼搏@

本文介紹了使用pow函數(shù)和自定義for循環(huán)計算冪的O(n)時間復(fù)雜度方法,然后重點講解了快速冪算法的分治思想,以及從二進制角度的解釋,包括如何通過位運算和循環(huán)迭代實現(xiàn)高效計算,給出了Java代碼實現(xiàn)

本文介紹了使用pow函數(shù)和自定義for循環(huán)計算冪的O(n)時間復(fù)雜度方法,然后重點講解了快速冪算法的分治思想,以及從二進制角度的解釋,包括如何通過位運算和循環(huán)迭代實現(xiàn)高效計算,給出了Java代碼實現(xiàn),

一、算法簡介

1.使用pow函數(shù)和自定義的for循環(huán)的時間復(fù)雜度為O(n)

/**計算x的y次方**/
//1.使用Pow函數(shù)
double res = Math.pow(x,y);
//2.自定義for循環(huán)
double res=x;
for(int i=1;i<y;i++){
     res=res*x;
}

2.快速冪的時間復(fù)雜度為O(log n)

二、快速冪的思想

（1）從分冶的角度出發(fā)，計算 $x^{y}$

①假設(shè)y為偶數(shù)，即計算 $3^{8}$

$3^{8}=3^{2*4}=9^{4}=9^{2*2}=81^{2}$ = $6561^{1}$

我們將指數(shù) y,每次劃分為 $\frac{y}{2}$ ,上述式子不需要進行8次循環(huán)，而只需要三步即可完成，注 $3^{2*4}$ 和 $9^{2*2}$ 是為了讓讀者好理解，而重復(fù)寫的。

②假設(shè)y為奇數(shù)，即計算 $3^{11}$

$3^{11}=3^{1+10}=3*3^{10}=3*9^{5}=3*9^{1+4}=3*9*81^{2}$ = $3*9*6561^{1}$

指數(shù)部分為奇數(shù)是可以化解成（1+偶數(shù)）的形式的，這樣我們可以把指數(shù)為1的底拿出來當(dāng)答案來乘，偶數(shù)部分同①繼續(xù)化解即可

偽代碼
    x=3,y=10,res=1
   while(指數(shù)y不等于0){
    if(指數(shù)y為奇數(shù)){
        res = res * x //提取底數(shù)出來，作為乘積
    }
    y=y/2 //指數(shù)二分
    x=x*x //底數(shù)平方

}

(2) 從二進制的角度出發(fā)

如8的二進制位：8= $1000_{2}$ ；

二進制轉(zhuǎn)十進制： $1000_{2}$ = $1*2^3+0*2^2+0*2^1+0*2^0$ =8

那么 $3^8=3^{(1000)_{2}}$ = $3^{1*2^3+0*2^2+0*2^1+0*2^0}$ = $3^{0*2^0}*3^{0*2^1}*3^{0*2^2}*3^{1*2^3}$ (倒序?qū)?

觀察發(fā)現(xiàn)：指數(shù)部分是由兩部分組成，第一部分是0001，第二部分是 $2^0,2^1,2^2,2^3$ ，發(fā)現(xiàn)2是循環(huán)增大的（用代碼x=x*x,循環(huán)迭代出來，但是否使用則看二進制位是否為‘1’），由于二進制要么為0要么為1（用代碼 y&1==1,來判斷）

再舉個詳細的例子(計算 $3^{11}$ )：

11=1011

$3^{11}=3^{1*2^{0}}*3^{1*2^{1}}*3^{0*2^{2}}*3^{1*2^{3}}$ = $3^{1*1}*3^{1*2}*3^{0*4}*3^{1*8}$

偽代碼：

 x=3,y=11,res=1

 while( （1011）y從尾往頭讀取){

  if( (y&1)==1){

     res=res*x;  //二進制位不為0，則相乘

     //如第一個1：res=1*3,    

     //第二個1：res=res*3^2

     //第三個數(shù)為0：不相乘，但x是不斷平方的，此時是x^4

     //第四個數(shù)為1：res=res*3^8  ,注意哦，平方是在if后面

       }

    二進制右移一位

    x=x*x; //依次迭代3^0,3^1,3^2，3^4,3^8................

 }

三、代碼實現(xiàn)

   public static double FastPow(int x,int y){
        double res= 1;
        while (y!=0){ 
            if(y%2 == 1){ //指數(shù)為奇數(shù)，也可以利用位運算：(y&1)==1 （與操作）： 判斷 n 二進制最右一位是否為 1
                res *= x;
            }
            y=y/2;  //指數(shù)循環(huán)二分,y>>=1 （移位操作）： n 右移一位（可理解為刪除最后一位,即除以2）。
            x=x*x;  //底數(shù)平分

        }
        return res;
    }

到此這篇關(guān)于Java中如何編寫一個數(shù)的n次方（冪運算）?的文章就介紹到這了,更多相關(guān)Java中的冪運算(冪函數(shù))內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！