[演算法] 指數運算 (Exponentiation)

[演算法] 指數運算 (Exponentiation)

   3月 31, 2018       PM

---

         現在很多程式語言內建就有包括指數運算的函式或運算子了，但如果今天你想要做的是矩陣的指數運算或著說程式內建函式庫沒有指數運算那該怎麼辦呢?

假設我要算 bⁿ，最直觀的想法為讓b自乘以n次

#python程式碼
def power(b, n):
    ans = 1
    for i in range(n):
        ans = ans * b
    return ans

不過問題是這樣程式執行起來很沒有效率，時間複雜度為O(n)。

-----------------------------------------------------------

我要來介紹另一種演算法叫 快速冪 :

假設我要算 b⁸， 與其讓b自乘以8次，我可以改用以下步驟來求得

1. b² = b · b 
2. b⁴ = b² · b²
3. b⁸ = b⁴ · b⁴

這樣從原本的8次運算變成只要3(log8)次就可以求出結果了。

把 bⁿ 的定義廣義化:

• 如果 n 等於 0:  b⁰  =  1
• 如果 n 是偶數: bⁿ  =  (b^n/2)²
• 如果 n 是奇數: bⁿ  =  b · b^n-1

#python程式碼
def fast_power(b, n):
    if(n==0):
        return 1
    else:
        if(n%2==0):
            pow_half = fast_power(b, n/2)
            return pow_half * pow_half
        else:
            return b * fast_power(b, n-1)

時間複雜度為(logn)

參考資料

• Structure and Interpretation of Computer Programs (SICP)

Read More