經典數學應用題 Pow(x, n) 計算 x的n次方

這題的題目在這裡:

題目敘述

題目會給定兩個參數，一個是底數x，一個是次方n。要求我們計算出x^n。

要求實作myPow(self, x: float, n: int) -> float 函數的內部邏輯。

也就是說，不可以呼叫程式語言內建計算指數的library

測試範例

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

約束條件

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n is an integer.
• Either x is not zero or n > 0.
• -104 <= xn <= 104

演算法

其實這題會用到大家在中學學過的指數律來進行的速算技巧，面對高次方時，可以先將高次方除以二，算出低次方的答案再平方回去，兩者會是等價的。

(x^m ) ^ n = x ^(mn)

(x 連乘m次) 再連乘n次 = x 連乘(mn)次

同理類推

x^n = (x^2)^(n/2)

x的n次方
= x 連乘 n 次 = (x平方) 再 連乘 n/2次
= x平方的 (n/2)次方
= (x^2)^(n/2)

定義Pow(x, n) 代表x的n次方

通則有兩種情況:

n是偶數時，Pow(x, n) = Pow(x*x, n //2 )

n是奇數時，Pow(x, n) = x * Pow(x*x, n //2 ) 注意 奇數的時候，需要補乘一個x

註:

n // 2 在python的語法裡面，相當於 n 除以 2，並且無條件捨去小數部分。
例如 7 // 2 = 3

例子:

x ^ 7 = x * (x^2) ^ 3

遞迴的終止條件:

n == 1 時，代表次方為1，x^n = x^1 = x 直接返回x 即可。

n == 0 時，代表次方為0，x^n = x^0 = 1 直接返回1 即可。

程式碼

class Solution:
　def myPow(self, x: float, n: int) -> float:
　　
　　if n == 0:
　　　# Base case:
　　　return 1.0
　　
　　elif n == 1:
　　　# Base case:
　　　return x
　　
　　elif n < 0:
　　　# General case:
　　　# x ^ (-n) = (1/x) ^ n
　　　return  self.myPow( 1/x, -n)
　　
　　
　　# Recurrence of fast power
　　
　　if n & 1:
　　　return x * self.myPow( x*x, n // 2)
　　else:
　　　return self.myPow( x*x, n // 2)

複雜度分析

時間複雜度:

O( log n ) 最多耗費O( log n ) 可以抵達終止條件。

空間複雜度:

O( log n ) 遞迴樹樹高 = 遞迴堆疊深度最深為O( log n )

可由遞迴關係 T( n ) = T( n / 2 ) + O( 1 ) 再經由Master Theorem 或者數學歸納法得到解答。

關鍵知識點

想到高次方可以藉由指數律來降階，從n次方降到1次方，做x^n的快速計算，比傳統O( n ) 逐項相乘的算法會快上許多。

在演算法實作上，背後對應到的框架就是DFS 和 Divide and Conquer分而治之法。

Reference:

[1] Python/JS/Go/C++ O( log n) by fast power. 85%+ [w/ Comment ] - Pow(x, n) - LeetCode