本篇通過(guò)一道面試題，一個(gè)面試場(chǎng)景，來(lái)好好分析一下如何求遞歸算法的時(shí)間復(fù)雜度。

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

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

這是為什么呢？

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

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

面試題：求x的n次方

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

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

	

	時(shí)間復(fù)雜度為O(n)，此時(shí)面試官會(huì)說(shuō)，有沒(méi)有效率更好的算法呢。

	如果此時(shí)沒(méi)有思路，不要說(shuō)：我不會(huì)，我不知道了等等。

	可以和面試官探討一下，詢(xún)問(wèn)：“可不可以給點(diǎn)提示”。面試官提示：“考慮一下遞歸算法”。

	那么就可以寫(xiě)出了如下這樣的一個(gè)遞歸的算法，使用遞歸解決了這個(gè)問(wèn)題。

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


	

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

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

	那再來(lái)看代碼，這里遞歸了幾次呢？

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

	這個(gè)時(shí)間復(fù)雜度就沒(méi)有達(dá)到面試官的預(yù)期。于是又寫(xiě)出了如下的遞歸算法的代碼：

	
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);
}



	

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

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

	

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

	這棵樹(shù)上每一個(gè)節(jié)點(diǎn)就代表著一次遞歸并進(jìn)行了一次相乘操作，所以進(jìn)行了多少次遞歸的話(huà)，就是看這棵樹(shù)上有多少個(gè)節(jié)點(diǎn)。

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

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

	

	時(shí)間復(fù)雜度忽略掉常數(shù)項(xiàng)-1之后，這個(gè)遞歸算法的時(shí)間復(fù)雜度依然是O(n)。對(duì)，你沒(méi)看錯(cuò)，依然是O(n)的時(shí)間復(fù)雜度！

	此時(shí)面試官就會(huì)說(shuō)：“這個(gè)遞歸的算法依然還是O(n)啊”， 很明顯沒(méi)有達(dá)到面試官的預(yù)期。

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

	想一想剛剛給出的那份遞歸算法的代碼，是不是有哪里比較冗余呢，其實(shí)有重復(fù)計(jì)算的部分。

	于是又寫(xiě)出如下遞歸算法的代碼：

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


	

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

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

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

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

	總結(jié)

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

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

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

	對(duì)于function3 這樣的遞歸實(shí)現(xiàn)，很容易讓人感覺(jué)這是O(logn)的時(shí)間復(fù)雜度，其實(shí)這是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);
}


	

	可以看出這道題目非常簡(jiǎn)單，但是又很考究算法的功底，特別是對(duì)遞歸的理解，這也是我面試別人的時(shí)候用過(guò)的一道題，所以整個(gè)情景我才寫(xiě)的如此逼真，哈哈。

	大廠面試的時(shí)候最喜歡用“簡(jiǎn)單題”來(lái)考察候選人的算法功底，注意這里的“簡(jiǎn)單題”可并不一定真的簡(jiǎn)單哦！

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

	原文標(biāo)題：關(guān)于遞歸算法的時(shí)間復(fù)雜度，你還不夠了解

	文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

	   審核編輯：彭靜