- 算法設計與分析:基于C++編程語言的描述
- 王秋芬 趙剛彬編著
- 917字
- 2024-12-13 09:52:13
1.4.4 遞歸算法的復雜性分析
1.遞歸算法的時間復雜性分析
一般而言,計算一個遞歸算法的時間復雜性可以遵循以下步驟:
(1)決定采用哪個(或哪些)參數作為輸入規模的度量。
(2)找出對算法的運行時間貢獻最大的語句作為基本語句。
(3)檢查一下,對于相同規模的不同輸入,基本語句的執行次數是否不同。如果不同,則需要從最好、最壞及平均三種情況進行討論。
(4)對于選定的基本語句的執行次數建立一個遞推關系式,并確定停止條件。
(5)通過計算該遞推關系式得到算法的漸進時間復雜性。
計算遞推關系式的方法有很多,最常用的便是后向代入法。該方法是從n出發,利用遞推關系,把n表示成n-1的函數關系,而n-1可以表示成n-2的函數關系,以此類推,直到停止條件為止。一般可以得到一個連加的形式,求解該連加式的值就可以得到漸進意義下的時間復雜性。
【例1-7】 以1.4.3節的排列問題為例討論如何分析遞歸算法的時間復雜性。
不難發現,當k=1時,已構成一個排列,第一個for循環需要執行n次操作將排列輸出;當k=n時,第二個for循環的循環體,對perm(A,k-1,n)執行n次調用。因此,排列算法perm對應的遞歸定義式為

采用后向代入法計算可得到通項公式,計算過程如下:
T(n)=nT(n-1)+nO(1)
=n(n-1)T(n-2)+n(n-1)O(1)+nO(1)
=n(n-1)(n-2)T(n-3)+n(n+1)(n-2)O(1)+n(n-1)O(1)+nO(1)
=…
=n(n-1)(n-2)…2T(1)n(n-1)(n-2)…2O(1)+…+nO(1)
=O(n!O(n(n-1)…2)+…+O(n)
所以,全排列算法perm的時間復雜性為Ω(n!)。
2.遞歸算法的空間復雜性分析
遞歸算法的空間復雜性指的是算法的遞歸深度,即算法在執行過程中所需的用于存儲“調用記錄”的遞歸棧的空間大小。
上述計算T(n)的過程共執行了n次遞推,可見perm算法的遞歸深度為n,由此可得,perm算法所需的遞歸棧的空間為O(n)。
另外,人們也常常采用構建遞歸樹的方法來對遞歸算法進行復雜性分析。這種方法較為方便且直觀形象,多年的實踐也證明了它是一個較好的分析工具。實際上,遞歸樹的思想是用樹來反映遞歸函數調用的次序,根結點代表主程序,其他結點代表所調用的子函數。算法運行時所需要的空間與遞歸樹的高度緊密相關——成正比,而樹中的結點數則反映了執行算法的關鍵步驟所需的時間。
- The Supervised Learning Workshop
- 兩周自制腳本語言
- C#完全自學教程
- QGIS:Becoming a GIS Power User
- 51單片機C語言開發教程
- 軟件供應鏈安全:源代碼缺陷實例剖析
- C# Multithreaded and Parallel Programming
- UML2面向對象分析與設計(第2版)
- Qlik Sense? Cookbook
- BeagleBone Robotic Projects(Second Edition)
- Java7程序設計入門經典
- Node.js區塊鏈開發
- 軟件設計模式(Java版)
- 軟硬件綜合系統軟件需求建模及可靠性綜合試驗、分析、評價技術
- Improving your Penetration Testing Skills