官术网_书友最值得收藏!

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(Ak-1,n)執行n次調用。因此,排列算法perm對應的遞歸定義式為

采用后向代入法計算可得到通項公式,計算過程如下:

Tn)=nTn-1)+nO(1)

=nn-1)Tn-2)+nn-1)O(1)+nO(1)

=nn-1)(n-2)Tn-3)+nn+1)(n-2)O(1)+nn-1)O(1)+nO(1)

=…

=nn-1)(n-2)…2T(1)nn-1)(n-2)…2O(1)+…+nO(1)

=On!Onn-1)…2)+…+On

所以,全排列算法perm的時間復雜性為Ωn!)。

2.遞歸算法的空間復雜性分析

遞歸算法的空間復雜性指的是算法的遞歸深度,即算法在執行過程中所需的用于存儲“調用記錄”的遞歸棧的空間大小。

上述計算Tn)的過程共執行了n次遞推,可見perm算法的遞歸深度為n,由此可得,perm算法所需的遞歸棧的空間為On)。

另外,人們也常常采用構建遞歸樹的方法來對遞歸算法進行復雜性分析。這種方法較為方便且直觀形象,多年的實踐也證明了它是一個較好的分析工具。實際上,遞歸樹的思想是用樹來反映遞歸函數調用的次序,根結點代表主程序,其他結點代表所調用的子函數。算法運行時所需要的空間與遞歸樹的高度緊密相關——成正比,而樹中的結點數則反映了執行算法的關鍵步驟所需的時間。

主站蜘蛛池模板: 江西省| 双桥区| 北碚区| 阳东县| 盘锦市| 股票| 宁晋县| 孙吴县| 渭南市| 揭阳市| 玛曲县| 邹城市| 剑阁县| 永春县| 尤溪县| 雷州市| 通榆县| 堆龙德庆县| 偏关县| 鲁甸县| 宣武区| 任丘市| 阳西县| 遂昌县| 石家庄市| 九龙坡区| 新田县| 甘孜| 皋兰县| 岳阳县| 全南县| 齐河县| 龙井市| 江口县| 封丘县| 营山县| 徐汇区| 怀集县| 东辽县| 文登市| 兴义市|