最近在刷OJ時(shí)候發(fā)現(xiàn)了一個(gè)問題疆股，那就是計(jì)算X^62盼樟，這是一個(gè)很簡單的問題，也很容易實(shí)現(xiàn)惕艳。這個(gè)問題有一個(gè)很容易的實(shí)現(xiàn)方案就是時(shí)間復(fù)雜度為logN的算法搞隐，就是計(jì)算62次X相乘。
代碼如下##
public static BigInteger pow(int x, int n) {
BigInteger result = BigInteger.ONE; // 初始化result為1
// BigeInteger的multiply方法需要BigInteger類型
BigInteger param = BigInteger.valueOf(x);
for (int i = 0; i < n; i++) {
result = result.multiply(param);
}
return result;
}
代碼很簡單远搪，但是如果是計(jì)算x^10000劣纲，甚至更多呢？雖然程序傾向如去做繁瑣重復(fù)的事情终娃， 但是顯然如果有效率更好的算法味廊，何樂而不為呢蒸甜？
分析##
對于冪運(yùn)算，是一個(gè)重復(fù)乘以常數(shù)的問題余佛。如果將這個(gè)問題拆解柠新，那么任何一個(gè)部分都是相似的，那么顯然辉巡，就可以用遞歸來解決這個(gè)問題恨憎。關(guān)于遞歸的問題可以參考我的另外一篇文章遞歸的基本法則。
思路##
對于遞歸郊楣，首先需要找到基本情形憔恳，當(dāng)N=1時(shí)，result=X净蚤；其次就是每一次遞歸都要朝基本情形進(jìn)行推進(jìn)钥组，對于此問題N=62而言，則可以按照如下方式拆解：
X^62 = X^31 * X^31, X^31 = (X^15 * X^15) * X, X^15 = (X^7 * X^7) * X,
X^7 = (X^3 * X^3) * X, X^3 = (x * x) *x.
以此類推,向基本類型推進(jìn)X=1推進(jìn)今瀑。
代碼##
public static BigInteger betterPow(BigInteger x, int n) {
if (n == 0) {
return 1;
}
if (n % 2 == 0) {
return betterPow(x.pow(2), n / 2);
} else {
return betterPow(x.pow(2), n / 2).multiply(x);
}
}
為了更好的理解上述代碼程梦，現(xiàn)在以betterPow(3,3)為例，分析代碼執(zhí)行過程：
首先是第一次執(zhí)行橘荠，betterPow(3,3) 等價(jià)于betterPow(9,1)*3∮旄剑現(xiàn)在的問題就變成了計(jì)算betterPow(9,1)，betterPow(9,1)等價(jià)于betterPow(81,0)*9「缤現(xiàn)在的問題就變成了計(jì)算betterPow(81,0)挺份，而當(dāng)n=0時(shí)是基本情形，所以betterPow(81,0)等于1贮懈。
所以最終計(jì)算公式為
betterPow(3,3)=betterPow(9,3)*3=betterPow(8,1)*9*3=1*9*3=27
可以看出匀泊，第一種解決方案用了62次乘法來計(jì)算X^62，而優(yōu)化后的方案則用了9次乘法運(yùn)算朵你。并且優(yōu)化后的方案最多需要的乘法次數(shù)為2logN探赫，遠(yuǎn)小于N。其復(fù)雜度為O（logN）撬呢。
