国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機(jī)構(gòu)

手機(jī)站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時隨地免費(fèi)學(xué)

千鋒教育

掃一掃進(jìn)入千鋒手機(jī)站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時隨地免費(fèi)學(xué)習(xí)課程

當(dāng)前位置:首頁  >  技術(shù)干貨  > 同樣的深度優(yōu)先搜索,使用棧和使用遞歸的性能差別是什么?

同樣的深度優(yōu)先搜索,使用棧和使用遞歸的性能差別是什么?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 07:33:00 1696980780

一、同樣的深度優(yōu)先搜索,使用棧和使用遞歸的性能差別

同樣的深度優(yōu)先搜索,使用棧和使用遞歸的性能差別是,對于內(nèi)存,棧的內(nèi)容太多了。只壓棧的話i和target應(yīng)該夠了,棧的內(nèi)容只需要和DP的參數(shù)一樣多。

遞歸

遞歸的基本思想是,把規(guī)模較大的一個問題,分解成規(guī)模較小的多個子問題去解決,而每一個子問題又可以繼續(xù)拆分成多個更小的子問題。最重要的一點(diǎn)就是假設(shè)子問題已經(jīng)解決了,現(xiàn)在要基于已經(jīng)解決的子問題來解決當(dāng)前問題;或者說,必須先解決子問題,再基于子問題來解決當(dāng)前問題。

遞歸解決的是有依賴順序關(guān)系的多個問題:假設(shè)一個抽象問題有兩個時間點(diǎn)要素:開始處理,結(jié)束處理,那么遞歸處理的順序就是,先開始處理的問題,最后才能結(jié)束處理。遞歸對問題的處理順序,是遵循了先入后出(也就是先開始的問題最后結(jié)束)的規(guī)律。

深度優(yōu)先搜索

深度優(yōu)先搜索(DFS)是用于在樹/圖中遍歷/搜索的另一種重要算法。也可以在更抽象的場景中使用。

正如樹的遍歷中所提到的,我們可以用 DFS 進(jìn)行 前序遍歷,中序遍歷 和 后序遍歷。在這三個遍歷順序中有一個共同的特性:除非我們到達(dá)最深的結(jié)點(diǎn),否則我們永遠(yuǎn)不會回溯。

這也是 DFS 和 BFS 之間最大的區(qū)別,BFS永遠(yuǎn)不會深入探索,除非它已經(jīng)在當(dāng)前層級訪問了所有結(jié)點(diǎn)。

延伸閱讀:

二、回溯是什么

回溯法采用試錯的思想,它嘗試分步的去解決一個問題。在分步解決問題的過程中,當(dāng)它通過嘗試發(fā)現(xiàn)現(xiàn)有的分步答案不能得到有效的正確的解答的時候,它將取消上一步甚至是上幾步的計(jì)算,再通過其它的可能的分步解答再次嘗試尋找問題的答案。

回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法:

系統(tǒng)性:在包含問題的所有解的解空間樹中,按照深度優(yōu)先的策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹;

跳躍性:算法搜索至解空間樹的任一結(jié)點(diǎn)時,判斷該結(jié)點(diǎn)為根的子樹是否包含問題的解,如果肯定不包含,則跳過以該結(jié)點(diǎn)為根的子樹的搜索,逐層向其祖先點(diǎn)回溯,否則,進(jìn)入該子樹,繼續(xù)深度優(yōu)先的策略進(jìn)行搜索。

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強(qiáng)師集結(jié),手把手帶你蛻變精英
請您保持通訊暢通,專屬學(xué)習(xí)老師24小時內(nèi)將與您1V1溝通
免費(fèi)領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
軟件架構(gòu)如何能夠滿足ASPICE流程?

一、軟件架構(gòu)如何能夠滿足ASPICE流程架構(gòu)的用途是把整個產(chǎn)品劃分為更為細(xì)節(jié)的板塊:軟件、硬件、通信等。在這個基礎(chǔ)上軟件整體將按照用途、功能...詳情>>

2023-10-11 08:47:00
紅黑樹為什么叫紅黑樹?

一、紅黑樹叫紅黑樹的原因紅黑樹(Red-Black Tree)是一種自平衡的二叉搜索樹(Binary Search Tree),其在插入和刪除操作時能夠自動調(diào)整樹的結(jié)...詳情>>

2023-10-11 08:42:41
為什么數(shù)組索引數(shù)據(jù)那么快速、有效?

一、數(shù)組索引數(shù)據(jù)快速、有效的原因1、連續(xù)內(nèi)存存儲數(shù)組在內(nèi)存中是連續(xù)存儲的,數(shù)組的元素在內(nèi)存中按照一定的順序排列,相鄰元素之間沒有間隔。...詳情>>

2023-10-11 08:36:19
數(shù)據(jù)結(jié)構(gòu)里的逐點(diǎn)插入法、排序二叉樹是什么?

一、數(shù)據(jù)結(jié)構(gòu)里的逐點(diǎn)插入法、排序二叉樹逐點(diǎn)插入法三角剖分是一種研究方法。三角剖分≠TIN三角剖分是代數(shù)拓?fù)鋵W(xué)里最基本的研究方法。 以曲面為...詳情>>

2023-10-11 08:08:01
在數(shù)據(jù)結(jié)構(gòu)中i=L->length是什么意思?

一、在數(shù)據(jù)結(jié)構(gòu)中i=L->length是什么意思在數(shù)據(jù)結(jié)構(gòu)中,i=L->length通常表示一個線性表L的長度,即L中元素的個數(shù)。線性表是一種數(shù)據(jù)結(jié)構(gòu),它由n...詳情>>

2023-10-11 07:54:48
快速通道