leetcode筆記：Pow(x, n)

leetcode筆記：Pow(x, n)

一. 題目描述

Implement pow(x, n).

二. 題目分析

實現pow(x, n)，即求x的n次冪。

最容易想到的方法就是用遞歸直接求n個x的乘積，這裡需要根據n的值，判斷結果是正數還是負數，這種方法的時間復雜度為O(n)。

更加快捷的方法是，使用分治法，對於x^n，有一下公式：

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

使用這種方法的時間復雜度為O(logn)。

三. 示例代碼

#include 

using namespace std;

class Solution {
public:
    double pow(double x, int n) 
    {
        if (n == 0)
            return 1;
        if (n > 0) 
            return power(x, n);
        else 
            return 1 / power(x, -1 * n);
        }

private:
    double power(double x, int n) 
    {
        if (n == 0) 
            return 1;
        double a = power(x, n / 2); // 遞歸求x^(n/2)
        if (n % 2 == 0) 
            return a * a;
        else 
            return a * a * x;
    }
};

四. 小結

此題為分治思路的經典題型之一。