傳送門：https://leetcode-cn.com/problems/powx-n/

一、LeetCode 50. Pow(x, n)

1、題目描述

實現 pow(x, n) ，即計算 x 的 n 次冪函數。

2、示例

示例 1:

輸入: 2.00000, 10 輸出: 1024.00000

示例 2:

輸入: 2.10000, 3 輸出: 9.26100

示例 3:

輸入: 2.00000, -2 輸出: 0.25000 解釋: 2-2 = 1/2^2 = 1/4 = 0.25

3、說明

-100.0 < x < 100.0
n 是 32 位有符號整數，其數值范圍是 [?231, 231 ? 1] 。

4、分析

本題重點在于邊界條件的分析和處理

• 如果 n < 0，是不是 n = -n， x = 1 / x ，再進行遞歸就能解決了呢？
• 如果 n = Intege.MIN_VALUE，n = -n 會出現溢出，怎么辦呢？
• 我們可以先將 n / 2 賦值給 a，再將 a = -n，就不會出現溢出問題。

5、實現

class Solution { public:double myPow(double x, int n) {if(n == 0)return 1;int a = n/2;if(n < 0){a = -a;x = 1.0/x;} double res = myPow(x, a);if(n % 2 == 0)return res * res;elsereturn res * res * x;} };

二、遞歸

1、定義

• 若一個對象部分的包含自己或用它自己給自己定義，則這個對象是遞歸的；
• 若一個過程直接或間接的調用自己，則這個過程是遞歸的。

2、思想

把問題分解為規模更小具有與原問題相同解法的子問題
==》優點：思考的方式更加簡單，程序也更加簡練。
==》缺點：增加了壓棧開銷，因此空間復雜度比較高。

3、遞歸條件

• 減小問題規模，并使子問題與原問題有相同解法。
• 設置出口，如果沒有出口那么程序會一直遞歸下去。

三、斐波那契數列

斐波那契數列是一個非常典型的遞歸問題。

1、循環方法

long Fibonacci1(size_t N) {long first = 1;long second = 1;long sum = 0;if(N < 3)return 1;else{for(size_t i = 3; i <= N; i++){sum = first + second;first = second;second = sum;}return sum;} }

==》時間復雜度：O(n)
==》空間復雜度：O(1)

2、遞歸方法1

long Fibonacci2(size_t N) {if(N < 3)return 1;elsereturn Fibonacci2(N-1) + Fibonacci2(N-2); }

==》由后向前計算
==》時間復雜度：O(n²)
==》空間復雜度：O(n)

3、遞歸方法2

long Fibonacci3(long first, long second, size_t N) {if(N < 3)return second;elsereturn Fibonacci3(second, first + second, N - 1); }

==》前向后計算——尾遞歸方法
==》在進行遞歸時函數只會使用第一次壓棧所開辟的棧空間，在一個棧空間內循環，而不會開辟別的棧空間，所以這種方式時間復雜度為O(N)，空間復雜度為O(1)，是一種非常高效的遞歸方式。

4、遞歸方法3

long *Fibonacci4(size_t N) {long *array = new long[N+1];if(N == 0)return NULL;array[0] = 1;array[1] = 1;for(size_t i = 2; i <= N; i++){array[i] = array[i-1] + array[i-2];}return array; }

四、遞歸函數的復雜度

在算法的分析中，當一個算法中包含遞歸調用時，其時間復雜度的分析==》一個遞歸方程的求解。

而對遞歸方程的求解，目前主流的方法：代入法，迭代法，公式法，母函數法，差分方程法。

1、代入法

• 首先要對這個問題的時間復雜度做出預測；
• 然后將預測帶入原來的遞歸方程，如果沒有出現矛盾，則是可能的解；
• 最后用數學歸納法證明。

示例
遞歸問題：T(n)=4T(n/2)+O(n)
（1）預測時間復雜度：O(n²)
（2）設T(n)=kn2（其中k為常數），將該結果帶入方程
（3）可得：左=kn2，右=4k(n/2)2+O(n)=kn2+O(n)
（4）由于n² 的階高于 n 的階，因而左右兩邊是相等的；
（5）數學歸納法進行驗證即可

2、迭代法

• 迭代的展開方程的右邊，直到沒有可以迭代的項為止；
• 這時通過對右邊的和進行估算來估計方程的解。
• 比較適用于分治問題的求解。

遞歸方程的一般形式

示例
（1）遞歸方程如下： $T(n)=2T(n/2)+n^2$

（2）迭代過程如下：
$$T(n)=2T(\frac{n}{2})+n^2$$$$=n^2+2((\frac{n}{2}{)}^2+2T(\frac{n}{4}))$$$$=n^2+2((\frac{n}{2}{)}^2+2((\frac{n}{4}{)}^2+2T(\frac{n}{8})))$$$$=n^2+2((\frac{n}{2}{)}^2+2((\frac{n}{4}{)}^2+...+2((\frac{n}{2^i}{)}^2+2T(\frac{n}{2^{i+1}}))))$$

容易知道，直到 $\frac{n}{2^{i+1}}=1$ 時，遞歸過程結束，這時我們計算如下：
　$$T(n)=n^2+2\frac{n^2}{2^2}+2^2\frac{n^2}{4^2}+2^2\frac{n^2}{8^2}+...$$$$=n^2(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...)$$$$=2n^2$$
==》該算法的時間復雜度：O(n²)

3、公式法

針對形如：T(n) = aT(n/b) + f(n)的遞歸方程
==》分治法的時間復雜度，即一個規模為n的問題被分成規模均為n/b的a個子問題，遞歸地求解這a個子問題，然后通過對這a個子問題的解的綜合，得到原問題的解。
==》公式法對于分治問題最好的解法

$$T(n)=?\begin{array}{ll}O(n^{lo{g}_{b}a}),& O(n^{lo{g}_{b}a})>O(f(n))\\ O(f(n)?logn),& O(n^{lo{g}_{b}a})=O(f(n))\\ O(f(n)),& O(n^{lo{g}_{b}a})<O(f(n))\end{array}$$
其中，$a>1,b>1$均為常數，$f(n)$是確定正函數。
==》分析：實際是比較$O(n^{lo{g}_{b}a})$和$O(f(n))$的階，若不等，則 $T(n)$ 取較大者；若階相等，則任選其一再乘以 $logn$即可。

注意
上面的公式并不包含所有的情況：$f(n)$是小于前者，但是并不是多項式的小于前者。

當 $f(n)=0$ 時，則有：
$$T(n)=\{\begin{array}{ll}O(n^{lo{g}_{b}a}),& a?=1\\ O(logn),& a=1\end{array}$$

4、母函數法

應用在一個無窮序列的冪級數，其遞歸形如：
$$T(n)=c_{1}T(n?1)+c_{2}T(n?2)+c_{3}T(n?3)+...++c_{k}T(n?k)+f(n)$$

示例——斐波那契數列
（1）遞歸公式：$T(n)=T(n?1)+T(n?2)$
（2）不妨設 $F(n)$ 為第 $n$ 項的運算量，可得：
$$F(n)=F(n?1)+F(n?2)$$
（3）構造母函數
$$\begin{gathered} G(x)=F(1)x+F(2)x^2+F(3)x^3+... \\ 可推導如下：F() \end{gathered}$$

總結

以上是生活随笔為你收集整理的【编程5】斐波那契数列 + 递归+LeetCode50的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。