遞歸演算法的時間複雜度？

01-05

T(m,n) = T(m-1,n) + T(m,n-1)
對於這樣一個遞歸演算法，其時間複雜度是多少呀？
問題背景：
在一個正方網格中，只能沿著網格往
上走或者往右走，求原點到指定坐標中有多少條路徑。

為此設置一個遞歸函數，當指定坐標（m，n）中的m==0或者n==0時，函數值為1.
除此之外的場合，等於其(m-1,n)和(m,n-1)路徑之和。
於是有T(m,n) = T(m-1,n) + T(m,n-1)遞歸演算法。但是時間複雜度實在不會算，看了主方法，遞歸樹等各種方法怎麼老感覺應用不上..
我自己算的結果是...不知道正不正確...

m+n choose m ......

遞歸展開之後你的結果其實是一條路徑一條路徑加起來的，所以至少就是你答案的量級

楊輝三角形轉45度。

如果單單迭代（即搜索），量級是2^n+2^m。

如果是記憶化搜索（即動規），量級是nm。

我解釋下我的思路，給個比大佬們更詳細點的時間複雜度演算法

首先，你要明白這個遞歸公式的結果等同於c(m+n，m)，圖像化來看就是m*n的網格，只能往下或者往右走，從坐上到右下的走法數量，f(i，j)表示坐標i j的走法數。

注意為了簡化，我這裡的i，j標註的是一個這樣一個網格中的點的坐標，也就是說m*n的網格總共有m+1 * n+1個點，最後算的是f(n，m)而終止條件是i==0或j==0

他既可以通過遞歸公式f(i-1，j)+f(i，j-1)，即到達該位置的方案等於從上面過來的方案數加上從左面過來的方案數，然後遞歸求解。

也可以通過排列組合公式，因為從原點0，0到這個點到i，j總共走了(i+j)步，這i+j步中有i步向下，計為d，j步向右，計為r，每一種走法都等於一個擁有i個d與j個r的字元序，這樣不同的字元序總共有C(i+j,i)個，即從i＋j個位置中選擇i個位置給i

做完了準備工作，開始說核心演算法:

這裡的時間複雜度，我們用遞歸中每個函數f(i,j)被call的次數的總和來算。當然，每次f(i,j)被call其實函數都只像同一個遞歸函數地址，我們認為的把i，j相同時候的調用看做是同一個函數。

那麼設t(i，j)為函數f(i,j)被調用的次數，每個棧的時間調用都是常數級，那麼時間複雜度則為

∑i=0 to n∑j=0 to m t(i,j)

最後就是t(i,j)怎麼算

每一次t(i，j)被call，也有兩種可能，就是從右邊call過來的跟從下邊call過來的，所以t(i，j)滿足遞歸公式

t(i,j) = t(i+1,j)+t(i,j+1)，終止條件為i==n || j == m

說白了，t f函數是一個旋轉180°對稱關係，為了好算，我們可以直接用f的總和來算t的總和

即時間複雜度等於

o(∑i∑jC(i+j,j))

然後根據時間複雜度的定義化簡，這個有空我上電腦補。

以上

題主的意思應該是在這個遞推式下直接遞歸的時間複雜度。

由題主給出的遞推式： $[left{ egin{array}{l} Tleft( {m,n} ight) = Tleft( {m,n - 1} ight) + Tleft( {m - 1,n} ight)\ Tleft( {0,n} ight) = Tleft( {m,0} ight) = 1 end{array} ight.]$ ，

我們可以用數學歸納法解出 $T(n,m)=C_{m+n}^n$ ，那麼時間複雜度就是 $O(C_{m+n}^n)$ 。但揣摩題主的意思，題主大概是想得到類似於線性，指數，對數這樣常見的複雜度。對於題主的結論，如果一定要問我我， $O(2^{m+n})$ 支持不支持，我說支持。由大O的定義，我們實際上只需要證明 $C_{m+n}^n leq 2^{m+n}$ 即可。實際上我們考察一下兩種排列：

假設現在有兩種蘋果，一種是紅色的(有 $m$ 個)，一種是綠色的(有 $n$ 個)，那麼這些蘋果的不全相異元素的全排列個數為 $C_{n+m}^n$ ，另一方面，對於 $m+n$ 個蘋果，要麼綠色，要麼紅色的話，一共有 $2^{m+n}$ 種可能。第一種情況當然是第二種情況的子集，於是 $C_{m+n}^n leq 2^{m+n}$ 。

—————題主可能不滿意分割線———————

常常我考慮組合數的規模都用斯特林公式 $n! sim sqrt{2pi n}cdot (frac{n}{e})^n$ 來估算，當然只有在 $n$ 足夠大的時候效果才好，但是單從量級上看，也可以用這個恆成立的不等式來估計： $(frac{n}{e})^n<n!<e(frac{n}{2})^n$ 。

那麼粗略估計一下：

$[C_{m + n}^n sim frac{{sqrt {2pi left( {m + n} ight)} cdot {{left( {m + n} ight)}^{m + n}}}}{{2pi sqrt {mn} cdot {n^n} cdot {m^m}}}]$

$[ = Oleft( {sqrt {frac{{m + n}}{{mn}}} cdot {{left( {1 + frac{n}{m}} ight)}^m} cdot {{left( {1 + frac{m}{n}} ight)}^n}} ight)]$

$[ = Oleft( {{{left( {1 + frac{n}{m}} ight)}^m} cdot {{left( {1 + frac{m}{n}} ight)}^n}} ight)]$

特別地，當 $m=n$ 時，上式化簡為 $O(2^{2n})$ 。再特別地，令 $n=1$ ，上式也可以退化為線性。上式也非常簡單放大到 $O(2^{n+m})$ ，等號成立條件也是 $m=n$ ，所以我覺得似乎題主的結論沒問題，最壞情況也是指數級沒毛病，只是界偏大了。（因為複雜度就是 $O(C_{m+n}^n)$ ）

可以先把遞歸表達式寫出來，然後做判斷。

或者先猜測一個界，而後用數學歸納法證明。

我想這個問題應該簡化後來討論，關於遞歸和動規，斐波那契額數列應該是強無敵，帶我回家開電腦來寫

哎呀，這只是個遞歸方程，具體看你怎麼實現了，就像斐波那契一樣，T(N)=T(N-1) + T(N-2)，依然可以控制在線性複雜度。

遞歸與循環在數學上等價，只是實現方式（一般情況下）不同而已。