導(dǎo)讀相信很多同學(xué)對遞歸算法的時間復(fù)雜度都很模糊，那么這篇來給大家通透的講一講。「同一道題目，同樣使用遞歸算法，有的同學(xué)會寫出了O(n)的代碼，有的同學(xué)就寫出了O....

相信很多同學(xué)對遞歸算法的時間復(fù)雜度都很模糊，那么這篇來給大家通透的講一講。

「同一道題目，同樣使用遞歸算法，有的同學(xué)會寫出了O(n)的代碼，有的同學(xué)就寫出了O(logn)的代碼」。

這是為什么呢？

如果對遞歸的時間復(fù)雜度理解的不夠深入的話，就會這樣！

那么我通過一道簡單的面試題，模擬面試的場景，來帶大家逐步分析遞歸算法的時間復(fù)雜度，最后找出最優(yōu)解，來看看同樣是遞歸，怎么就寫成了O(n)的代碼。

面試題：求x的n次方

想一下這么簡單的一道題目，代碼應(yīng)該如何寫呢。最直觀的方式應(yīng)該就是，一個for循環(huán)求出結(jié)果，代碼如下：

intfunction1(intx,intn){intresult=1;//注意任何數(shù)的0次方等于1for(inti=0;i<n;i ){result=result*x;}returnresult;}

時間復(fù)雜度為O(n)，此時面試官會說，有沒有效率更好的算法呢。

「如果此時沒有思路，不要說：我不會，我不知道了等等」。

可以和面試官探討一下，詢問：“可不可以給點提示”。面試官提示：“考慮一下遞歸算法”。

那么就可以寫出了如下這樣的一個遞歸的算法，使用遞歸解決了這個問題。

intfunction2(intx,intn){if(n==0){return1;//return1同樣是因為0次方是等于1的}returnfunction2(x,n-1)*x;}

面試官問：“那么這個代碼的時間復(fù)雜度是多少？”。

一些同學(xué)可能一看到遞歸就想到了O(logn)，其實并不是這樣，遞歸算法的時間復(fù)雜度本質(zhì)上是要看: 「遞歸的次數(shù) * 每次遞歸中的操作次數(shù)」。

那再來看代碼，這里遞歸了幾次呢？

每次n-1，遞歸了n次時間復(fù)雜度是O(n)，每次進行了一個乘法操作，乘法操作的時間復(fù)雜度一個常數(shù)項O(1)，所以這份代碼的時間復(fù)雜度是 n * 1 = O(n)。

這個時間復(fù)雜度就沒有達到面試官的預(yù)期。于是又寫出了如下的遞歸算法的代碼：

intfunction3(intx,intn){if(n==0){return1;}if(n%2==1){returnfunction3(x,n/2)*function3(x,n/2)*x;}returnfunction3(x,n/2)*function3(x,n/2);}

面試官看到后微微一笑，問：“這份代碼的時間復(fù)雜度又是多少呢？” 此刻有些同學(xué)可能要陷入了沉思了。

我們來分析一下，首先看遞歸了多少次呢，可以把遞歸抽象出一顆滿二叉樹。剛剛同學(xué)寫的這個算法，可以用一顆滿二叉樹來表示（為了方便表示，選擇n為偶數(shù)16），如圖：

遞歸算法的時間復(fù)雜度

當(dāng)前這顆二叉樹就是求x的n次方，n為16的情況，n為16的時候，進行了多少次乘法運算呢？

這棵樹上每一個節(jié)點就代表著一次遞歸并進行了一次相乘操作，所以進行了多少次遞歸的話，就是看這棵樹上有多少個節(jié)點。

熟悉二叉樹話應(yīng)該知道如何求滿二叉樹節(jié)點數(shù)量，這顆滿二叉樹的節(jié)點數(shù)量就是2^3 2^2 2^1 2^0 = 15，可以發(fā)現(xiàn)：「這其實是等比數(shù)列的求和公式，這個結(jié)論在二叉樹相關(guān)的面試題里也經(jīng)常出現(xiàn)」。

這么如果是求x的n次方，這個遞歸樹有多少個節(jié)點呢，如下圖所示：(m為深度，從0開始)

「時間復(fù)雜度忽略掉常數(shù)項-1之后，這個遞歸算法的時間復(fù)雜度依然是O(n)」。對，你沒看錯，依然是O(n)的時間復(fù)雜度！

此時面試官就會說：“這個遞歸的算法依然還是O(n)啊”， 很明顯沒有達到面試官的預(yù)期。

那么O(logn)的遞歸算法應(yīng)該怎么寫呢？

想一想剛剛給出的那份遞歸算法的代碼，是不是有哪里比較冗余呢。

于是又寫出如下遞歸算法的代碼：

intfunction4(intx,intn){if(n==0){return1;}intt=function4(x,n/2);//這里相對于function3，是把這個遞歸操作抽取出來if(n%2==1){returnt*t*x;}returnt*t;}

再來看一下現(xiàn)在這份代碼時間復(fù)雜度是多少呢？

依然還是看他遞歸了多少次，可以看到這里僅僅有一個遞歸調(diào)用，且每次都是n/2 ，所以這里我們一共調(diào)用了log以2為底n的對數(shù)次。

「每次遞歸了做都是一次乘法操作，這也是一個常數(shù)項的操作，那么這個遞歸算法的時間復(fù)雜度才是真正的O(logn)」。

此時大家最后寫出了這樣的代碼并且將時間復(fù)雜度分析的非常清晰，相信面試官是比較滿意的。

總結(jié)

對于遞歸的時間復(fù)雜度，畢竟初學(xué)者有時候會迷糊，刷過很多題的老手依然迷糊。

「本篇我用一道非常簡單的面試題目：求x的n次方，來逐步分析遞歸算法的時間復(fù)雜度，注意不要一看到遞歸就想到了O(logn)！」

同樣使用遞歸，有的同學(xué)可以寫出O(logn)的代碼，有的同學(xué)還可以寫出O(n)的代碼。

對于function3 這樣的遞歸實現(xiàn)，很容易讓人感覺這是O(logn)的時間復(fù)雜度，其實這是O(n)的算法！

intfunction3(intx,intn){if(n==0){return1;}if(n%2==1){returnfunction3(x,n/2)*function3(x,n/2)*x;}returnfunction3(x,n/2)*function3(x,n/2);}

可以看出這道題目非常簡單，但是又很考究算法的功底，特別是對遞歸的理解，這也是我面試別人的時候用過的一道題，所以整個情景我才寫的如此逼真，哈哈。

大廠面試的時候最喜歡用“簡單題”來考察候選人的算法功底，注意這里的“簡單題”可并不一定真的簡單哦！

如果認(rèn)真讀完本篇，相信大家對遞歸算法的有一個新的認(rèn)識的，同一道題目，同樣是遞歸，效率可是不一樣的！

就醬，「代碼隨想錄」是技術(shù)公眾號里的一抹清流，值得介紹給身邊的朋友同學(xué)們！

打算從頭開始打卡的錄友，可以在「算法匯總」這里找到歷史文章，很多錄友都在從頭打卡，你并不孤單！

-------end-------

我將算法學(xué)習(xí)相關(guān)的資料已經(jīng)整理到了Github ：https://github.com/youngyangyang04/leetcode-master，里面還有l(wèi)eetcode刷題攻略、各個類型經(jīng)典題目刷題順序、思維導(dǎo)圖看一看一定會有所收獲，如果給你有幫助給一個star支持一下吧！

我是程序員Carl，個人主頁：https://github.com/youngyangyang04

更多精彩點擊下方了解更多！