javaScript 算法基礎(chǔ)知識第 4 部分:具有線性時間復(fù)雜度 O(n) 和指數(shù)時間復(fù)雜度 O(2^n) 的遞歸算法。遞歸是編程中的關(guān)鍵概念之一。作為一種解決問題的方法,它也被廣泛用于數(shù)據(jù)結(jié)構(gòu)和算法中。它幫助我們將大型復(fù)雜問題分解為較小的問題。因此,了解遞歸的時間復(fù)雜性對于理解和提高代碼效率至關(guān)重要。
對于本系列 JavaScript 算法的第 3 部分,您可以參考以下鏈接。
第3部分:使用漸近分析推導(dǎo)恒定時間復(fù)雜度O(1)
在本文中,我們將介紹遞歸算法的兩個示例及其時間復(fù)雜度。
具有線性時間復(fù)雜度 O(n) 的遞歸算法
具有指數(shù)時間復(fù)雜度 O(2^n) 的遞歸算法
首先,簡要介紹一下遞歸。
什么是遞歸?
我們說一個函數(shù)是遞歸函數(shù),如果它直接或間接地調(diào)用自己。下面是遞歸函數(shù)的一瞥。
上面的函數(shù)是遞歸函數(shù)的一個例子,因為它正在調(diào)用自身,但它也是不完整的,因為它會導(dǎo)致無限循環(huán)。這是因為該函數(shù)沒有任何退出條件。但是,這里的關(guān)鍵點是,遞歸只是從該函數(shù)內(nèi)部調(diào)用該函數(shù)。
為了非常清楚地說明這一點,讓我們看一個簡單的例子。
示例問題
創(chuàng)建一個簡單的函數(shù)來計算輸入數(shù)字的階乘。
如果您不知道什么是階乘,請使用以下輸入查看以下函數(shù)的行為。
你拿輸入數(shù)字,乘以這個數(shù)字減去1,然后重復(fù)相同的操作,直到你達(dá)到1。這就是我們計算階乘的方式。而且,最后,我們可以編寫一個函數(shù)來做到這一點。
讓我們首先看一下非遞歸方法。因為遞歸通常(并非總是)只是常規(guī)循環(huán)的替代方法。因此,讓我們嘗試首先使用基于循環(huán)的方法解決它。
功能(基于循環(huán)的方法)
因此,這是一個使用正態(tài)循環(huán)的階乘函數(shù)。使用這樣的循環(huán)并不是解決階乘問題的壞方法。但也存在一種不同的方法來使用遞歸來解決上述問題。而且,正如您將進(jìn)一步看到的那樣,這種遞歸將允許我們編寫更少的代碼,這通常是我們可能想要使用遞歸的原因之一。
遞歸解 O(n)
上面的函數(shù)是遞歸的,因為它正在調(diào)用自身。在函數(shù)中有兩件重要的事情要觀察,即“if block”和“函數(shù)調(diào)用”,參數(shù)為(n-1)。
我們將 if 塊稱為“退出條件”或始終返回值的“基本情況”。并且,將“函數(shù)調(diào)用”作為“遞歸步驟”。
另一件需要注意的重要事情是,我們在遞歸步驟中將不同的參數(shù)傳遞給函數(shù)調(diào)用。因為,如果我們再次調(diào)用帶有n的函數(shù),我們將不會更改任何內(nèi)容。我們只會得到一個無限循環(huán)。
因此,遞歸函數(shù)應(yīng)始終具有這兩個組件,即“退出條件”和“遞歸步驟”,否則我們將始終具有無限循環(huán),這將使我們的程序崩潰。
如果滿足基本條件,退出條件或基本情況為我們提供了一種退出函數(shù)的方法。
而且,遞歸步驟幫助我們通過對同一函數(shù)進(jìn)行遞歸調(diào)用來計算結(jié)果,但輸入的大小減小。
這可以表示為函數(shù)調(diào)用鏈。就像下面的例子一樣,對于一個事實(4),我們將返回4 * fact(3),這給了我們3 * 個事實(2),這將再次給我們2 * 個事實(1)。并且,這最終返回 1,然后將計算的返回值傳遞給函數(shù)調(diào)用,從而產(chǎn)生 24。
如何推導(dǎo)遞歸算法的時間復(fù)雜度?
根據(jù)漸近分析,我們?nèi)匀豢梢杂嬎闵鲜龊瘮?shù)中的操作。因此,每個操作將執(zhí)行一次,包括 return 語句中的函數(shù)調(diào)用。
但是,由于我們在 return 語句中有一個函數(shù)調(diào)用。我們啟動一個新的函數(shù)調(diào)用,因此函數(shù)中的所有代碼都會再次運(yùn)行多次,直到滿足退出條件。因此,我們可以計算遞歸函數(shù)的函數(shù)調(diào)用次數(shù)。因此,我們可以看到,在上面的示例中,我們得到了 4 個函數(shù)調(diào)用,函數(shù)的階乘為 4。
在每個函數(shù)調(diào)用中,我們有一個常量時間,我們的函數(shù)中沒有任何循環(huán)。因此,我們可以將其編寫如下。
但是,上述函數(shù)調(diào)用觸發(fā)了多個函數(shù)調(diào)用,即當(dāng)輸入值為n時,n個函數(shù)調(diào)用。
因此,我們對多個函數(shù)調(diào)用的時間復(fù)雜度將是,
那就是,
這可以寫成,
上面的等式最后只是O(n)。而且,這與我們基于循環(huán)的解決方案的時間復(fù)雜度相同,即線性時間復(fù)雜度。
雖然這是遞歸算法的一個非常簡單的示例,但我們也有使用遞歸的算法,因為它們比替代解決方案產(chǎn)生更好的結(jié)果。
遞歸算法 指數(shù)時間復(fù)雜度 O(2^n)
在前面的示例中,遞歸看起來不錯,我們通??梢跃帉懜俚拇a來解決問題。但是,讓我告訴你,遞歸并不總是最好的解決方案。為了證明這一點,我們將研究斐波那契數(shù)列的遞歸實現(xiàn)。
功能
上述函數(shù)是一個斐波那契函數(shù),它啟動兩個遞歸函數(shù),觸發(fā)新的函數(shù)調(diào)用,直到滿足退出條件。解析所有這些函數(shù)調(diào)用后,結(jié)果將冒泡并返回到初始函數(shù)。此處的這兩個函數(shù)中的每一個都將返回一個值,然后將這些值相加。
那么,這種方法有什么問題呢?
這種方法的錯誤之處在于,當(dāng)我們調(diào)用它時,該函數(shù)會構(gòu)建一個跨多個分支的嵌套遞歸函數(shù)調(diào)用樹。
這可以在下面的示例圖中看到,因為n = 4。
如您所見,我們收到了 9 個函數(shù)調(diào)用,例如 4 個。如果我們使用基于循環(huán)的解決方案來完成它,那么我們只會迭代4次。這不是一個好的解決方案,因為即使對于較小的輸入數(shù)字(如 4),函數(shù)調(diào)用也有大約 9 次執(zhí)行。
類似地,函數(shù)調(diào)用呈指數(shù)級增長,輸入數(shù)字從 4 線性增加到 6,如下所示。
如果輸入數(shù)字進(jìn)一步增加,情況會變得更糟。
那么這個遞歸函數(shù)的時間復(fù)雜度是多少呢?
這絕對不是O(n),基于循環(huán)的解決方案就是這種情況。我們得到了(9)4次處決,(15)次處決5次,(25)執(zhí)行6次處決。因此,如果我們僅將提供給函數(shù)的數(shù)量增加 1,則執(zhí)行次數(shù)將呈指數(shù)級增長。它不是線性增長的。我們添加的執(zhí)行次數(shù)似乎隨著n的增大而增長,并且呈指數(shù)級增長。
因此,這里相對較小的上升需要越來越長的時間。事實上,這個時間尺度的復(fù)雜性是指數(shù)級的。隨著n的每個增量,我們向這個遞歸樹添加全新的分支,而不僅僅是一個函數(shù)調(diào)用。此外,每個分支都由其他分支組成。結(jié)果,這很快增加到我們的機(jī)器無法處理的體積。因此,對于我們已經(jīng)有一個線性時間復(fù)雜度解決方案的問題,這是一個可怕的解決方案。像這樣的遞歸函數(shù)說明了它不如基于循環(huán)的解決方案。這需要更多的時間。雖然它可能看起來很優(yōu)雅,但這是一個可怕的解決方案。
這是一個指數(shù)時間復(fù)雜度 O(2^n)。我們確定了函數(shù)調(diào)用的增長,并且由于其指數(shù),我們可以說該算法具有指數(shù)時間復(fù)雜性。