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

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

　　第3部分：使用漸近分析推導(dǎo)恒定時(shí)間復(fù)雜度O(1)

　　在本文中，我們將介紹遞歸算法的兩個(gè)示例及其時(shí)間復(fù)雜度。

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

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

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

　　什么是遞歸？

　　我們說一個(gè)函數(shù)是遞歸函數(shù)，如果它直接或間接地調(diào)用自己。下面是遞歸函數(shù)的一瞥。

　　上面的函數(shù)是遞歸函數(shù)的一個(gè)例子，因?yàn)樗谡{(diào)用自身，但它也是不完整的，因?yàn)樗鼤?huì)導(dǎo)致無限循環(huán)。這是因?yàn)樵摵瘮?shù)沒有任何退出條件。但是，這里的關(guān)鍵點(diǎn)是，遞歸只是從該函數(shù)內(nèi)部調(diào)用該函數(shù)。

　　為了非常清楚地說明這一點(diǎn)，讓我們看一個(gè)簡單的例子。

　　示例問題

　　創(chuàng)建一個(gè)簡單的函數(shù)來計(jì)算輸入數(shù)字的階乘。

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

　　你拿輸入數(shù)字，乘以這個(gè)數(shù)字減去1，然后重復(fù)相同的操作，直到你達(dá)到1。這就是我們計(jì)算階乘的方式。而且，最后，我們可以編寫一個(gè)函數(shù)來做到這一點(diǎn)。

　　讓我們首先看一下非遞歸方法。因?yàn)檫f歸通常(并非總是)只是常規(guī)循環(huán)的替代方法。因此，讓我們嘗試首先使用基于循環(huán)的方法解決它。

　　功能(基于循環(huán)的方法)

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

　　遞歸解 O(n)

　　上面的函數(shù)是遞歸的，因?yàn)樗谡{(diào)用自身。在函數(shù)中有兩件重要的事情要觀察，即“if block”和“函數(shù)調(diào)用”，參數(shù)為(n-1)。

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

　　另一件需要注意的重要事情是，我們在遞歸步驟中將不同的參數(shù)傳遞給函數(shù)調(diào)用。因?yàn)椋绻覀冊俅握{(diào)用帶有n的函數(shù)，我們將不會(huì)更改任何內(nèi)容。我們只會(huì)得到一個(gè)無限循環(huán)。

　　因此，遞歸函數(shù)應(yīng)始終具有這兩個(gè)組件，即“退出條件”和“遞歸步驟”，否則我們將始終具有無限循環(huán)，這將使我們的程序崩潰。

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

　　而且，遞歸步驟幫助我們通過對同一函數(shù)進(jìn)行遞歸調(diào)用來計(jì)算結(jié)果，但輸入的大小減小。

　　這可以表示為函數(shù)調(diào)用鏈。就像下面的例子一樣，對于一個(gè)事實(shí)(4)，我們將返回4 * fact(3)，這給了我們3 * 個(gè)事實(shí)(2)，這將再次給我們2 * 個(gè)事實(shí)(1)。并且，這最終返回 1，然后將計(jì)算的返回值傳遞給函數(shù)調(diào)用，從而產(chǎn)生 24。

　　如何推導(dǎo)遞歸算法的時(shí)間復(fù)雜度？

　　根據(jù)漸近分析，我們?nèi)匀豢梢杂?jì)算上述函數(shù)中的操作。因此，每個(gè)操作將執(zhí)行一次，包括 return 語句中的函數(shù)調(diào)用。

　　但是，由于我們在 return 語句中有一個(gè)函數(shù)調(diào)用。我們啟動(dòng)一個(gè)新的函數(shù)調(diào)用，因此函數(shù)中的所有代碼都會(huì)再次運(yùn)行多次，直到滿足退出條件。因此，我們可以計(jì)算遞歸函數(shù)的函數(shù)調(diào)用次數(shù)。因此，我們可以看到，在上面的示例中，我們得到了 4 個(gè)函數(shù)調(diào)用，函數(shù)的階乘為 4。

　　在每個(gè)函數(shù)調(diào)用中，我們有一個(gè)常量時(shí)間，我們的函數(shù)中沒有任何循環(huán)。因此，我們可以將其編寫如下。

　　但是，上述函數(shù)調(diào)用觸發(fā)了多個(gè)函數(shù)調(diào)用，即當(dāng)輸入值為n時(shí)，n個(gè)函數(shù)調(diào)用。

　　因此，我們對多個(gè)函數(shù)調(diào)用的時(shí)間復(fù)雜度將是，

　　那就是，

　　這可以寫成，

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

　　雖然這是遞歸算法的一個(gè)非常簡單的示例，但我們也有使用遞歸的算法，因?yàn)樗鼈儽忍娲鉀Q方案產(chǎn)生更好的結(jié)果。

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

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

　　功能

　　上述函數(shù)是一個(gè)斐波那契函數(shù)，它啟動(dòng)兩個(gè)遞歸函數(shù)，觸發(fā)新的函數(shù)調(diào)用，直到滿足退出條件。解析所有這些函數(shù)調(diào)用后，結(jié)果將冒泡并返回到初始函數(shù)。此處的這兩個(gè)函數(shù)中的每一個(gè)都將返回一個(gè)值，然后將這些值相加。

　　那么，這種方法有什么問題呢？

　　這種方法的錯(cuò)誤之處在于，當(dāng)我們調(diào)用它時(shí)，該函數(shù)會(huì)構(gòu)建一個(gè)跨多個(gè)分支的嵌套遞歸函數(shù)調(diào)用樹。

　　這可以在下面的示例圖中看到，因?yàn)閚 = 4。

　　如您所見，我們收到了 9 個(gè)函數(shù)調(diào)用，例如 4 個(gè)。如果我們使用基于循環(huán)的解決方案來完成它，那么我們只會(huì)迭代4次。這不是一個(gè)好的解決方案，因?yàn)榧词箤τ谳^小的輸入數(shù)字(如 4)，函數(shù)調(diào)用也有大約 9 次執(zhí)行。

　　類似地，函數(shù)調(diào)用呈指數(shù)級(jí)增長，輸入數(shù)字從 4 線性增加到 6，如下所示。

　　如果輸入數(shù)字進(jìn)一步增加，情況會(huì)變得更糟。

　　那么這個(gè)遞歸函數(shù)的時(shí)間復(fù)雜度是多少呢？

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

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

　　這是一個(gè)指數(shù)時(shí)間復(fù)雜度 O(2^n)。我們確定了函數(shù)調(diào)用的增長，并且由于其指數(shù)，我們可以說該算法具有指數(shù)時(shí)間復(fù)雜性。