遞歸演算法的時間複雜度是:【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中文網其他相關文章!

C#和.NET適用於Web、桌面和移動開發。 1)在Web開發中,ASP.NETCore支持跨平台開發。 2)桌面開發使用WPF和WinForms,適用於不同需求。 3)移動開發通過Xamarin實現跨平台應用。

C#.NET生態系統提供了豐富的框架和庫,幫助開發者高效構建應用。 1.ASP.NETCore用於構建高性能Web應用,2.EntityFrameworkCore用於數據庫操作。通過理解這些工具的使用和最佳實踐,開發者可以提高應用的質量和性能。

如何將C#.NET應用部署到Azure或AWS?答案是使用AzureAppService和AWSElasticBeanstalk。 1.在Azure上,使用AzureAppService和AzurePipelines自動化部署。 2.在AWS上,使用AmazonElasticBeanstalk和AWSLambda實現部署和無服務器計算。

C#和.NET的結合為開發者提供了強大的編程環境。 1)C#支持多態性和異步編程,2).NET提供跨平台能力和並發處理機制,這使得它們在桌面、Web和移動應用開發中廣泛應用。

.NETFramework是一個軟件框架,C#是一種編程語言。 1..NETFramework提供庫和服務,支持桌面、Web和移動應用開發。 2.C#設計用於.NETFramework,支持現代編程功能。 3..NETFramework通過CLR管理代碼執行,C#代碼編譯成IL後由CLR運行。 4.使用.NETFramework可快速開發應用,C#提供如LINQ的高級功能。 5.常見錯誤包括類型轉換和異步編程死鎖,調試需用VisualStudio工具。

C#是一種由微軟開發的現代、面向對象的編程語言,.NET是微軟提供的開發框架。 C#結合了C 的性能和Java的簡潔性,適用於構建各種應用程序。 .NET框架支持多種語言,提供垃圾回收機制,簡化內存管理。

C#和.NET運行時緊密合作,賦予開發者高效、強大且跨平台的開發能力。 1)C#是一種類型安全且面向對象的編程語言,旨在與.NET框架無縫集成。 2).NET運行時管理C#代碼的執行,提供垃圾回收、類型安全等服務,確保高效和跨平台運行。

要開始C#.NET開發,你需要:1.了解C#的基礎知識和.NET框架的核心概念;2.掌握變量、數據類型、控制結構、函數和類的基本概念;3.學習C#的高級特性,如LINQ和異步編程;4.熟悉常見錯誤的調試技巧和性能優化方法。通過這些步驟,你可以逐步深入C#.NET的世界,並編寫高效的應用程序。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

Safe Exam Browser
Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

PhpStorm Mac 版本
最新(2018.2.1 )專業的PHP整合開發工具

MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

VSCode Windows 64位元 下載
微軟推出的免費、功能強大的一款IDE編輯器