程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Pow(x, n)

leetcode筆記:Pow(x, n)

編輯:關於C++

一. 題目描述

Implement pow(x, n).

二. 題目分析

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

最容易想到的方法就是用遞歸直接求nx的乘積,這裡需要根據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;
    }
};

這裡寫圖片描述

四. 小結

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


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved