搜尋
首頁後端開發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++ lambda 表达式是否支持递归?C++ lambda 表达式是否支持递归?Apr 17, 2024 pm 09:06 PM

是的,C++Lambda表达式可以通过使用std::function支持递归:使用std::function捕获Lambda表达式的引用。通过捕获的引用,Lambda表达式可以递归调用自身。

递归程序在C++中找到数组的最小和最大元素递归程序在C++中找到数组的最小和最大元素Aug 31, 2023 pm 07:37 PM

我们以整数数组Arr[]作为输入。目标是使用递归方法在数组中找到最大和最小的元素。由于我们使用递归,我们将遍历整个数组,直到达到长度=1,然后返回A[0],这形成了基本情况。否则,将当前元素与当前最小或最大值进行比较,并通过递归更新其值以供后续元素使用。让我们看看这个的各种输入输出场景−输入 −Arr={12,67,99,76,32};输出 −数组中的最大值:99解释 &mi

在Java中递归地计算子字符串出现的次数在Java中递归地计算子字符串出现的次数Sep 17, 2023 pm 07:49 PM

给定两个字符串str_1和str_2。目标是使用递归过程计算字符串str1中子字符串str2的出现次数。递归函数是在其定义中调用自身的函数。如果str1是"Iknowthatyouknowthatiknow",str2是"know"出现次数为-3让我们通过示例来理解。例如输入str1="TPisTPareTPamTP",str2="TP";输出Countofoccurrencesofasubstringrecursi

如何解决Python的最大递归深度错误?如何解决Python的最大递归深度错误?Jun 24, 2023 pm 02:48 PM

Python是一门易学易用的编程语言,然而在使用Python编写递归函数时,可能会遇到递归深度过大的错误,这时就需要解决这个问题。本文将为您介绍如何解决Python的最大递归深度错误。1.了解递归深度递归深度是指递归函数嵌套的层数。在Python默认情况下,递归深度的限制是1000,如果递归的层数超过这个限制,系统就会报错。这种报错通常称为“最大递归深度错误

如何使用Vue表单处理实现表单的递归嵌套如何使用Vue表单处理实现表单的递归嵌套Aug 11, 2023 pm 04:57 PM

如何使用Vue表单处理实现表单的递归嵌套引言:随着前端数据处理和表单处理的复杂性不断增加,我们需要通过一种灵活的方式来处理复杂的表单。Vue作为一种流行的JavaScript框架,为我们提供了许多强大的工具和特性来处理表单的递归嵌套。本文将向大家介绍如何使用Vue来处理这种复杂的表单,并附上代码示例。一、表单的递归嵌套在某些场景下,我们可能需要处理递归嵌套的

如何在Linux中使用递归“ls”如何在Linux中使用递归“ls”Mar 20, 2024 am 10:03 AM

在Linux系统中,“ls”命令是一个非常有用的工具,它提供了对当前目录中文件和文件夹的简洁概述。通过“ls”命令,您可以快速查看文件和文件夹的权限、属性等重要信息。虽然“ls”命令是一个基本的命令,但是通过结合不同的子命令和选项,它可以成为系统管理员和用户的重要工具。通过熟练使用“ls”命令及其各种选项,您可以更高效地管理文件系统,快速定位所需文件,以及执行各种操作。因此,“ls”命令不仅可以帮助您了解当前目录结构,还可以提高您的工作效率。比如,在Linux系统中,通过使用带有递归选项的"ls

Go语言中的循环和递归的比较研究Go语言中的循环和递归的比较研究Jun 01, 2023 am 09:23 AM

注:本文以Go语言的角度来比较研究循环和递归。在编写程序时,经常会遇到需要对一系列数据或操作进行重复处理的情况。为了实现这一点,我们需要使用循环或递归。循环和递归都是常用的处理方式,但在实际应用中,它们各有优缺点,因此在选择使用哪种方法时需要考虑实际情况。本文将对Go语言中的循环和递归进行比较研究。一、循环循环是一种重复执行某段代码的机制。Go语言中主要有三

利用ThinkPHP6实现递归树结构利用ThinkPHP6实现递归树结构Jun 20, 2023 pm 02:48 PM

随着互联网的发展,各种网站和应用程序中都出现了树形结构的展示,例如分类目录、人员组织架构、权限管理等。在这些应用场景中,递归树结构已经成为了非常重要且实用的模型之一。ThinkPHP6是一种基于MVC模型的PHP开发框架,其拥有丰富的扩展库和优秀的性能,广受开发者的认可和使用,而在ThinkPHP6中实现递归树结构也变得更加方便了。下面,我们将介绍如何在Th

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脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前By尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
4 週前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具