如何找到遞歸函數的時間復雜度?

讓我們首先了解求時間復雜度的基本概念。我們假設程序中的每條語句都需要一個單位的時間來執行。

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

同樣，我們假設每條語句都需要一個單位時間。如果該語句重復多次，那么我們需要計算它執行多少次的頻率。這足以分析我們的功能。

查找遞歸函數的時間復雜度的示例：

我們將使用以下函數。也就是說，我們將計算以下遞歸函數的時間復雜度。

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

打印需要多少時間?

打印需要一個單位的時間。

printf 在那里寫了多少次?

那里只寫了一次 printf。但這是一個遞歸函數。所以，它一次又一次地呼喚自己。

由于它是一個遞歸函數，讓我們找出 printf 函數執行了多少次。正如我們在遞歸工作原理一文中已經討論過的，我們可以使用跟蹤樹或遞歸樹來找出這一點。

正如您在上面的跟蹤樹中看到的，它首先打印值 3，然后打印 2，然后打印值 1。這意味著 printf 語句執行了 3 次。因此，當 n 值為 3 時，此遞歸函數將需要 3 個單位的時間來執行。如果我們將 n 值設為 5，那么執行此遞歸函數將需要 5 個單位的時間。

所以，我們可以說對于 n 它將花費 n 個單位的時間。回到這個例子，如果我們必須在書架上放一本書。你需要一個單位的時間，10本書你需要10個單位的時間。因此，對于 n 本書，您將獲得 n 個時間單位。您需要記住的最重要的一點是時間取決于書籍的數量。

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

使用遞歸關系的時間復雜度：

還有另一種方法可以找到時間復雜度，即使用遞歸關系。讓我們看看如何編寫遞歸關系以及如何解決它以找到遞歸函數的時間復雜度。現在，讓我們使用遞歸關系計算以下遞歸函數的時間復雜度。

我們假設上述函數花費的時間是 T(n)，其中 T 代表時間。如果 fun1() 花費的時間是 T(n)，那么總時間應該是該函數內的語句所花費的所有時間的總和。

那么，讓我們看一下聲明。每條語句都需要一個單位的時間來執行。請參閱函數內部有一個條件語句(if (n > 0))。執行需要多少時間，只需執行一個單位時間。然后是一個printf語句，這也需要一個單位時間。

然后那里多了一個函數調用語句(fun1(n-1))，需要多少時間，也需要一個單位時間。不，這是不正確的。它不會花費一個單位的時間。這是一個函數調用。它應該是該功能所花費的總時間。這不僅僅是一個正常的說法。它會再次調用自己。所以，在那之后還有更多的東西。那么，我們需要知道該函數調用需要多少時間?

讓我們仔細看看。我們所說的 fun1(int n) 函數調用，總時間是 T(n)。那么這個fun1(n-1)和fun1(int n)類似，這里是n-1。所以，這個函數所花費的總時間將是 T(n-1) 時間。那么什么是T(n)?正如我們所說的聲明所花費的所有時間的總和。因此，讓我們取T(n) =T(n-1)+2的總和。為了更好地理解，請看下圖。

因此，當n>0時，遞歸關系為T(n)=T(n-1 )+ 2。當n=0時會發生什么，它只會檢查條件，它不會進入其中并會出來。只是檢查條件，所以需要一個單位的時間。為了更好地理解，請看下圖。

所以，這是由 fun1 函數形成的遞歸。因此，遞歸函數的時間復雜度可以用遞歸關系的形式表示。