文章目錄
- 題目
- 思路
- int的取值范圍
- 快速冪
- 從二進制的角度來理解
- 從二分法的角度來理解
- 代碼
- 復雜度分析
題目
實作 pow(x, n) ，即計算 x 的 n 次冪函式（即，xn），不得使用庫函式，同時不需要考慮大數問題，
示例 1：
輸入：x = 2.00000, n = 10
輸出：1024.00000
示例 2：
輸入：x = 2.10000, n = 3
輸出：9.26100
示例 3：
輸入：x = 2.00000, n = -2
輸出：0.25000
解釋：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
思路
想用累乘處理冪路子就走窄了，超時是板上釘釘的，
用快速冪的思想才符合題目考察的意圖，在詳說快速冪之前說一個很刁鉆的測驗用例 —— n=-2147483648，
int的取值范圍
我們知道：
- int的取值范圍是
-2147483648（-231）到2147483647（231 - 1） -2147483648有一位符號位可用，因此2147483647是32位作業系統中最大的符號型整型常量，- 當出現這個刁鉆的測驗用例時，如果對n粗暴的取絕對值的話，int是容納不下的，因此當
n<0時， 需要定義一個long long型別變數m來存盤n的絕對值，
快速冪
從二進制的角度來理解
- 對于任何十進制正整數 n ，設其二進制為
則有：
- 根據以上推導，可把計算 xn 轉化為解決以下兩個問題：
- 因此，應用以上操作，可在回圈中依次計算
的值，并將所有
累計相乘即可，
從二分法的角度來理解
快速冪實際上是二分思想的一種應用，
- 二分推導： xn = xn/2 × xn/2 = （x2)n/2，令
n/2為整數，則需要分為奇偶兩種情況（設向下取整除法符號為 “//” ）：
- 冪獲取結果：
- 根據二分推導，可通過回圈 x = x2 操作，每次把冪從
n降至n//2，直至將冪降為0； - 設
sum=1，則初始狀態 xn = xn × sum，在回圈二分時，每當n為奇數時，將多出的一項x乘入sum，則最終可化至 xn = x0 * sum = sum，回傳sum即可，
轉自作者：jyd
演算法流程：
- 當
x = 0時：直接回傳 0 （避免后續x = 1 / x操作報錯）， - 初始化
sum = 1； - 當
n < 0時：把問題轉化至n≥0的范圍內，即執行x = 1/x，n = - n； - 回圈計算：當
n = 0時跳出；
- 當
n&1=1時：將當前x乘入sum（即sum?=x）； - 執行 x = x2（即
x?=x）； - 執行
n右移一位（即n>>=1），
- 回傳 sum，
代碼
class Solution {
public:
double myPow(double x, int n) {
if(x == 0) return 0;
double sum = 1;
long long m = n;
if(n < 0){
x = 1.0/x;
m = -m;
}
while(m > 0){
if(m & 1){
sum *= x;
}
x *= x;
m >>= 1;
}
return sum;
}
};
復雜度分析
- 時間復雜度 O(log_2 n)： 二分的時間復雜度為對數級別，
- 空間復雜度 O(1)： sum， b 等變數占用常數大小額外空間，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282617.html
標籤：其他
上一篇：計算機網路之網路分層結構
下一篇：學習筆記-java基礎-網路編程