跟大家講解下有關遞歸算法的時間復雜度是什么，相信小伙伴們對這個話題應該也很關注吧，現在就為小伙伴們說說遞歸算法的時間復雜度是什么，小編也收集到了有關遞歸算法的時間復雜度是什么的相關資料，希望大家看到了會喜歡。

遞歸算法的時間復雜度是：【T(n)=o(f(n))】，它表示隨問題規模n的增大，算法的執行時間增長率和f(n)增長率成正比，這稱作算法的漸進時間復雜度。

遞歸算法的時間復雜度

時間復雜度：

一般情況下，算法中基本操作重復的次數就是問題規模n的某個函數f（n），進而分析f（n）隨n的變化情況并確定T（n）的數量級。這里用‘o’來表示數量級，給出算法時間復雜度。

T（n）=o（f（n））；

它表示隨問題規模n的增大，算法的執行時間增長率和f（n）增長率成正比，這稱作算法的漸進時間復雜度。而我們一般情況下討論的最壞的時間復雜度。

推薦課程：C語言教程

空間復雜度：

算法的空間復雜度并不是實際占用的空間，而是計算整個算法空間輔助空間單元的個數，與問題的規模沒有關系。算法的空間復雜度S（n）定義為該算法所耗費空間的數量級。

S（n）=o（f（n））

若算法執行所需要的輔助空間相對于輸入數據n而言是一個常數，則稱這個算法空間復雜度輔助空間為o（1）；

遞歸算法空間復雜度：遞歸深度n*每次遞歸所要的輔助空間，如果每次遞歸所需要的輔助空間為常數，則遞歸空間復雜度o（n）。

遞歸算法時間復雜度的計算方程式是一個遞歸方程：

在引入遞歸樹之前可以考慮一個例子：

T(n) = 2T(n/2) + n2

迭代2次可以得：

T(n) = n2 + 2(2T(n/4) + (n/2) 2)

還可以繼續迭代，將其完全展開可得：

T(n) = n2 + 2((n/2) 2 +2((n/22)2 + 2((n/23) 2 +2((n/24) 2 +…+2((n/2i) 2 +2T(n/2i + 1)))…))))……(1)

而當n/2i+1 == 1時，迭代結束。

將(1)式小括號展開，可得：

T(n) = n2 + 2(n/2)2 +22(n/22) 2 + … + 2i(n/2i)2 +2i+1T(n/2i+1)

這恰好是一個樹形結構，由此可引出遞歸樹法。

圖中的(a)(b)(c)(d)分別是遞歸樹生成的第1,2,3,n步。每一節點中都將當前的自由項n2留在其中，而將兩個遞歸項T(n/2)+ T(n/2)分別攤給了他的兩個子節點，如此循環。

圖中所有節點之和為:

[1 + 1/2 + (1/2)2 + (1/2)3 + … + (1/2)i] n2 = 2n2

可知其時間復雜度為O(n2)

可以得到遞歸樹的規則為：

(1)每層的節點為T(n) = kT(n / m) + f(n)中的f(n)在當前的n/m下的值；

(2)每個節點的分支數為k；

(3)每層的右側標出當前層中所有節點的和。

再舉個例子：

T(n) = T(n/3) + T(2n/3) + n

其遞歸樹如下圖所示：

可見每層的值都為n，從根到葉節點的最長路徑是：

因為最后遞歸的停止是在(2/3)kn == 1.則

于是　　

即T(n) = O(nlogn)　

總結，利用此方法解遞歸算法復雜度：

f(n) = af(n/b) + d(n)

1.當d(n)為常數時：

　　

2.當d(n) = cn 時：

3.當d(n)為其他情況時可用遞歸樹進行分析。

由第二種情況知，若采用分治法對原算法進行改進，則著重點是采用新的計算方法縮小a值。　　

以上就是遞歸算法的時間復雜度是什么的詳細內容，更多請關注php中文網其它相關文章！

來源：php中文網