搜尋
首頁後端開發C#.Net教程遞歸演算法的時間複雜度是什麼

遞歸演算法的時間複雜度是什麼

Oct 24, 2019 am 10:53 AM
時間複雜度遞迴

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

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
C#.NET用於網絡,桌面和移動開發C#.NET用於網絡,桌面和移動開發Apr 25, 2025 am 12:01 AM

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

C#.NET生態系統:框架,庫和工具C#.NET生態系統:框架,庫和工具Apr 24, 2025 am 12:02 AM

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

將C#.NET應用程序部署到Azure/AWS:逐步指南將C#.NET應用程序部署到Azure/AWS:逐步指南Apr 23, 2025 am 12:06 AM

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

C#.NET:強大的編程語言簡介C#.NET:強大的編程語言簡介Apr 22, 2025 am 12:04 AM

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

.NET框架與C#:解碼術語.NET框架與C#:解碼術語Apr 21, 2025 am 12:05 AM

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

揭開c#.net的神秘面紗:初學者的概述揭開c#.net的神秘面紗:初學者的概述Apr 20, 2025 am 12:11 AM

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

C#和.NET運行時:它們如何一起工作C#和.NET運行時:它們如何一起工作Apr 19, 2025 am 12:04 AM

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

C#.NET開發:入門的初學者指南C#.NET開發:入門的初學者指南Apr 18, 2025 am 12:17 AM

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

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

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

熱工具

Safe Exam Browser

Safe Exam Browser

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

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

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

MantisBT

MantisBT

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

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器