如何找到遞歸函數(shù)的時(shí)間復(fù)雜度?

讓我們首先了解求時(shí)間復(fù)雜度的基本概念。我們假設(shè)程序中的每條語(yǔ)句都需要一個(gè)單位的時(shí)間來(lái)執(zhí)行。

讓我給出那個(gè)背后的想法。假設(shè)有一些書(shū)存放在一個(gè)地方，您必須移動(dòng)這本書(shū)并將其放在架子或架子上。需要多少時(shí)間?也許半秒，四分之一秒，也許如果有人工作得很慢，可能需要一秒鐘才能把一本書(shū)放在那里。時(shí)間因人而異。所以，我們不說(shuō)秒或毫秒，我們說(shuō)一個(gè)時(shí)間單位。如果以貨幣為例，一美元，一盧比，一英鎊。我們說(shuō)一個(gè)，但市場(chǎng)價(jià)值可能會(huì)有所不同。所以，我們說(shuō)一美元或一單位貨幣。

同樣，我們假設(shè)每條語(yǔ)句都需要一個(gè)單位時(shí)間。如果該語(yǔ)句重復(fù)多次，那么我們需要計(jì)算它執(zhí)行多少次的頻率。這足以分析我們的功能。

查找遞歸函數(shù)的時(shí)間復(fù)雜度的示例：

我們將使用以下函數(shù)。也就是說(shuō)，我們將計(jì)算以下遞歸函數(shù)的時(shí)間復(fù)雜度。

現(xiàn)在，讓我們看看上面的函數(shù)(fun1)在做什么。它什么都不做，只是打印。它只是打印 n 的值。

打印需要多少時(shí)間?

打印需要一個(gè)單位的時(shí)間。

printf 在那里寫(xiě)了多少次?

那里只寫(xiě)了一次 printf。但這是一個(gè)遞歸函數(shù)。所以，它一次又一次地呼喚自己。

由于它是一個(gè)遞歸函數(shù)，讓我們找出 printf 函數(shù)執(zhí)行了多少次。正如我們?cè)谶f歸工作原理一文中已經(jīng)討論過(guò)的，我們可以使用跟蹤樹(shù)或遞歸樹(shù)來(lái)找出這一點(diǎn)。

正如您在上面的跟蹤樹(shù)中看到的，它首先打印值 3，然后打印 2，然后打印值 1。這意味著 printf 語(yǔ)句執(zhí)行了 3 次。因此，當(dāng) n 值為 3 時(shí)，此遞歸函數(shù)將需要 3 個(gè)單位的時(shí)間來(lái)執(zhí)行。如果我們將 n 值設(shè)為 5，那么執(zhí)行此遞歸函數(shù)將需要 5 個(gè)單位的時(shí)間。

所以，我們可以說(shuō)對(duì)于 n 它將花費(fèi) n 個(gè)單位的時(shí)間。回到這個(gè)例子，如果我們必須在書(shū)架上放一本書(shū)。你需要一個(gè)單位的時(shí)間，10本書(shū)你需要10個(gè)單位的時(shí)間。因此，對(duì)于 n 本書(shū)，您將獲得 n 個(gè)時(shí)間單位。您需要記住的最重要的一點(diǎn)是時(shí)間取決于書(shū)籍的數(shù)量。

時(shí)間可以表示為 n 的順序，即O(n)。花費(fèi)的時(shí)間是n的順序。

使用遞歸關(guān)系的時(shí)間復(fù)雜度：

還有另一種方法可以找到時(shí)間復(fù)雜度，即使用遞歸關(guān)系。讓我們看看如何編寫(xiě)遞歸關(guān)系以及如何解決它以找到遞歸函數(shù)的時(shí)間復(fù)雜度。現(xiàn)在，讓我們使用遞歸關(guān)系計(jì)算以下遞歸函數(shù)的時(shí)間復(fù)雜度。

我們假設(shè)上述函數(shù)花費(fèi)的時(shí)間是 T(n)，其中 T 代表時(shí)間。如果 fun1() 花費(fèi)的時(shí)間是 T(n)，那么總時(shí)間應(yīng)該是該函數(shù)內(nèi)的語(yǔ)句所花費(fèi)的所有時(shí)間的總和。

那么，讓我們看一下聲明。每條語(yǔ)句都需要一個(gè)單位的時(shí)間來(lái)執(zhí)行。請(qǐng)參閱函數(shù)內(nèi)部有一個(gè)條件語(yǔ)句(if (n > 0))。執(zhí)行需要多少時(shí)間，只需執(zhí)行一個(gè)單位時(shí)間。然后是一個(gè)printf語(yǔ)句，這也需要一個(gè)單位時(shí)間。

然后那里多了一個(gè)函數(shù)調(diào)用語(yǔ)句(fun1(n-1))，需要多少時(shí)間，也需要一個(gè)單位時(shí)間。不，這是不正確的。它不會(huì)花費(fèi)一個(gè)單位的時(shí)間。這是一個(gè)函數(shù)調(diào)用。它應(yīng)該是該功能所花費(fèi)的總時(shí)間。這不僅僅是一個(gè)正常的說(shuō)法。它會(huì)再次調(diào)用自己。所以，在那之后還有更多的東西。那么，我們需要知道該函數(shù)調(diào)用需要多少時(shí)間?

讓我們仔細(xì)看看。我們所說(shuō)的 fun1(int n) 函數(shù)調(diào)用，總時(shí)間是 T(n)。那么這個(gè)fun1(n-1)和fun1(int n)類(lèi)似，這里是n-1。所以，這個(gè)函數(shù)所花費(fèi)的總時(shí)間將是 T(n-1) 時(shí)間。那么什么是T(n)?正如我們所說(shuō)的聲明所花費(fèi)的所有時(shí)間的總和。因此，讓我們?nèi)(n) =T(n-1)+2的總和。為了更好地理解，請(qǐng)看下圖。

因此，當(dāng)n>0時(shí)，遞歸關(guān)系為T(mén)(n)=T(n-1 )+ 2。當(dāng)n=0時(shí)會(huì)發(fā)生什么，它只會(huì)檢查條件，它不會(huì)進(jìn)入其中并會(huì)出來(lái)。只是檢查條件，所以需要一個(gè)單位的時(shí)間。為了更好地理解，請(qǐng)看下圖。

所以，這是由 fun1 函數(shù)形成的遞歸。因此，遞歸函數(shù)的時(shí)間復(fù)雜度可以用遞歸關(guān)系的形式表示。