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

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 遞歸算法及其時間復雜度 O(n) 與 O(2^n)

遞歸算法及其時間復雜度 O(n) 與 O(2^n)

來源:千鋒教育
發布人:syq
時間: 2022-09-21 11:35:10 1663731310

  javaScript 算法基礎知識第 4 部分:具有線性時間復雜度 O(n) 和指數時間復雜度 O(2^n) 的遞歸算法。遞歸是編程中的關鍵概念之一。作為一種解決問題的方法,它也被廣泛用于數據結構和算法中。它幫助我們將大型復雜問題分解為較小的問題。因此,了解遞歸的時間復雜性對于理解和提高代碼效率至關重要。

1

  對于本系列 JavaScript 算法的第 3 部分,您可以參考以下鏈接。

  第3部分:使用漸近分析推導恒定時間復雜度O(1)

  在本文中,我們將介紹遞歸算法的兩個示例及其時間復雜度。

  具有線性時間復雜度 O(n) 的遞歸算法

  具有指數時間復雜度 O(2^n) 的遞歸算法

  首先,簡要介紹一下遞歸。

  什么是遞歸?

  我們說一個函數是遞歸函數,如果它直接或間接地調用自己。下面是遞歸函數的一瞥。

2

  上面的函數是遞歸函數的一個例子,因為它正在調用自身,但它也是不完整的,因為它會導致無限循環。這是因為該函數沒有任何退出條件。但是,這里的關鍵點是,遞歸只是從該函數內部調用該函數。

  為了非常清楚地說明這一點,讓我們看一個簡單的例子。

  示例問題

  創建一個簡單的函數來計算輸入數字的階乘。

  如果您不知道什么是階乘,請使用以下輸入查看以下函數的行為。

3

  你拿輸入數字,乘以這個數字減去1,然后重復相同的操作,直到你達到1。這就是我們計算階乘的方式。而且,最后,我們可以編寫一個函數來做到這一點。

4

  讓我們首先看一下非遞歸方法。因為遞歸通常(并非總是)只是常規循環的替代方法。因此,讓我們嘗試首先使用基于循環的方法解決它。

  功能(基于循環的方法)

5

  因此,這是一個使用正態循環的階乘函數。使用這樣的循環并不是解決階乘問題的壞方法。但也存在一種不同的方法來使用遞歸來解決上述問題。而且,正如您將進一步看到的那樣,這種遞歸將允許我們編寫更少的代碼,這通常是我們可能想要使用遞歸的原因之一。

  遞歸解 O(n)

6

  上面的函數是遞歸的,因為它正在調用自身。在函數中有兩件重要的事情要觀察,即“if block”和“函數調用”,參數為(n-1)。

  我們將 if 塊稱為“退出條件”或始終返回值的“基本情況”。并且,將“函數調用”作為“遞歸步驟”。

  另一件需要注意的重要事情是,我們在遞歸步驟中將不同的參數傳遞給函數調用。因為,如果我們再次調用帶有n的函數,我們將不會更改任何內容。我們只會得到一個無限循環。

  因此,遞歸函數應始終具有這兩個組件,即“退出條件”和“遞歸步驟”,否則我們將始終具有無限循環,這將使我們的程序崩潰。

  如果滿足基本條件,退出條件或基本情況為我們提供了一種退出函數的方法。

  而且,遞歸步驟幫助我們通過對同一函數進行遞歸調用來計算結果,但輸入的大小減小。

  這可以表示為函數調用鏈。就像下面的例子一樣,對于一個事實(4),我們將返回4 * fact(3),這給了我們3 * 個事實(2),這將再次給我們2 * 個事實(1)。并且,這最終返回 1,然后將計算的返回值傳遞給函數調用,從而產生 24。

7

  如何推導遞歸算法的時間復雜度?

  根據漸近分析,我們仍然可以計算上述函數中的操作。因此,每個操作將執行一次,包括 return 語句中的函數調用。

  但是,由于我們在 return 語句中有一個函數調用。我們啟動一個新的函數調用,因此函數中的所有代碼都會再次運行多次,直到滿足退出條件。因此,我們可以計算遞歸函數的函數調用次數。因此,我們可以看到,在上面的示例中,我們得到了 4 個函數調用,函數的階乘為 4。

  在每個函數調用中,我們有一個常量時間,我們的函數中沒有任何循環。因此,我們可以將其編寫如下。

8

  但是,上述函數調用觸發了多個函數調用,即當輸入值為n時,n個函數調用。

  因此,我們對多個函數調用的時間復雜度將是,

9

  那就是,

10

  這可以寫成,

11

  上面的等式最后只是O(n)。而且,這與我們基于循環的解決方案的時間復雜度相同,即線性時間復雜度。

  雖然這是遞歸算法的一個非常簡單的示例,但我們也有使用遞歸的算法,因為它們比替代解決方案產生更好的結果。

  遞歸算法 指數時間復雜度 O(2^n)

  在前面的示例中,遞歸看起來不錯,我們通常可以編寫更少的代碼來解決問題。但是,讓我告訴你,遞歸并不總是最好的解決方案。為了證明這一點,我們將研究斐波那契數列的遞歸實現。

  功能

12

  上述函數是一個斐波那契函數,它啟動兩個遞歸函數,觸發新的函數調用,直到滿足退出條件。解析所有這些函數調用后,結果將冒泡并返回到初始函數。此處的這兩個函數中的每一個都將返回一個值,然后將這些值相加。

  那么,這種方法有什么問題呢?

  這種方法的錯誤之處在于,當我們調用它時,該函數會構建一個跨多個分支的嵌套遞歸函數調用樹。

  這可以在下面的示例圖中看到,因為n = 4。

13

  如您所見,我們收到了 9 個函數調用,例如 4 個。如果我們使用基于循環的解決方案來完成它,那么我們只會迭代4次。這不是一個好的解決方案,因為即使對于較小的輸入數字(如 4),函數調用也有大約 9 次執行。

  類似地,函數調用呈指數級增長,輸入數字從 4 線性增加到 6,如下所示。

14

  如果輸入數字進一步增加,情況會變得更糟。

  那么這個遞歸函數的時間復雜度是多少呢?

  這絕對不是O(n),基于循環的解決方案就是這種情況。我們得到了(9)4次處決,(15)次處決5次,(25)執行6次處決。因此,如果我們僅將提供給函數的數量增加 1,則執行次數將呈指數級增長。它不是線性增長的。我們添加的執行次數似乎隨著n的增大而增長,并且呈指數級增長。

  因此,這里相對較小的上升需要越來越長的時間。事實上,這個時間尺度的復雜性是指數級的。隨著n的每個增量,我們向這個遞歸樹添加全新的分支,而不僅僅是一個函數調用。此外,每個分支都由其他分支組成。結果,這很快增加到我們的機器無法處理的體積。因此,對于我們已經有一個線性時間復雜度解決方案的問題,這是一個可怕的解決方案。像這樣的遞歸函數說明了它不如基于循環的解決方案。這需要更多的時間。雖然它可能看起來很優雅,但這是一個可怕的解決方案。

  這是一個指數時間復雜度 O(2^n)。我們確定了函數調用的增長,并且由于其指數,我們可以說該算法具有指數時間復雜性。

tags:
聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT