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

遞歸算法應(yīng)該都不陌生，其實(shí)最開始遇見遞歸應(yīng)該是在數(shù)學(xué)課上，類似于f(x)=f(x-1)+f(x+1)，f(1)=1，f(2)=4，f(3)=3這種數(shù)學(xué)題大家應(yīng)該見過不少，其實(shí)思想就是層層遞歸，最終將目標(biāo)值用f(1)，f(2)，f(3)表示。

之前做了一個需求，需要實(shí)現(xiàn)類似操作系統(tǒng)文件夾的功能，我們用MySQL數(shù)據(jù)庫記錄數(shù)據(jù)，表字段有4列，分別是id，index_name，pid，is_directory，index_name記錄文件或文件的名字，pid記錄它的父級id，is_directory標(biāo)記它是文件還是文件夾。

記錄被存下以后，就涉及到取數(shù)據(jù)的問題了，我們前端需要的目標(biāo)數(shù)據(jù)結(jié)構(gòu)是這樣的：

[{"id":1,"name":"./"},{"id":2,"name":"./1.txt"},
{"id":3,"name":"./dir1/"},
{"id":4,"name":"./dir1/2.txt"},...]

有點(diǎn)類似linux系統(tǒng)的tree命令。

第一版代碼是這樣的：

tree = []
def getTree(pid):
              return
for index in childIndexes:
 if len(tree) == 0:
   if index.is_directory==1                            tree.append(
{'id':index.id,'name':'./'+index.index_name+'/'})                     
getTree(index.id)
                     else:                            
tree.append(
{'id':index.id,'name':'/'+index.index_name})
              else: 
                    for item in tree:  
if item['id'] == index.id
                                   if item.is_directory==1:                                          tree.append({'id':index.id,'name': 
item['name']+index.index_name+'/'})    
                               else:  
                                        tree.append
(
{'id':index.id,'name':item['name']+index.index_name
}
)

大概看一下這個算法的時間復(fù)雜度，第一層的遍歷時間復(fù)雜度是n，第二層遍歷的時間復(fù)雜度是n，內(nèi)層的時間復(fù)雜度是O（n^2），再加上遞歸，最后的時間復(fù)雜度是O（2^n*n^2），這個算法可見很粗糙，假如遞歸深度到是100，最后執(zhí)行效率簡直會讓人頭皮發(fā)麻。接下來我們考慮一下如何優(yōu)化。

第二版代碼：

tree = []
def getTree(pid,path='./'):
              return
       for index in childIndexes:
             if len(tree) == 0: 
                    if index.is_directory==1                            tree.append({'id':index.id,
'name':path+index.index_name+'/'}) 
                           getTree(index.id, 
path+index.index_name+'/')
                    else:
                           tree.append({'id':index.id,
'name':path+index.index_name}) 
             else: 
                    if item.is_directory==1:                            tree.append({'id':index.id,
'name':path+index.index_name+'/'})
                     else: 
                           tree.append({'id':index.id,
'name':path+index.index_name})

我們用變量保存每一次的path，這次我們看看時間復(fù)雜度是多少。第一層遍歷時間復(fù)雜度是O(n)，加上遞歸，最后的時間復(fù)雜度是O(2^n*n)，不算太理想，最起碼比第一次好點(diǎn)。

再看看一個面試的常見的題目，斐波拉契數(shù)列，n=1,1,3,5,8,13...，求第n位是多少？

一看首先就想到了遞歸的方式：

def fibSquence(n):     
  if n in (1,2):       
   return 
   fibSquence(n-1)+ fibSquence(n-2)

這個算法的時間復(fù)雜度是O(2^n)，關(guān)于時間復(fù)雜度具體看調(diào)用次數(shù)便能明白。我們考慮一下如何優(yōu)化，比如求n=3是，需要先求n=2,n=1，但是最開始n=1,n=2已經(jīng)求過，多了兩步重復(fù)計算。

下面是優(yōu)化的代碼：

fibMap = {1:1,2:2}
def fibSquence(n):
       else:
        result = fibSquence(n-1)+ fibSquence(n-2)              fibMap.update({n:result})
              return result

我們用map報存中間值，map是基于hash實(shí)現(xiàn)的，時間復(fù)雜度是O(1)，這樣這個算法的時間復(fù)雜度就是O(n)。

但是事實(shí)上這個問題大可不必用遞歸方式求解。

fibMap = {1:1,2:2}
def fibSquence(n):
       else:
              for i in range(3,n+1): 
                    fibMap.update({i:fibMap[i-1]+fibMap[i-2]})
              return fibMap[n]

這樣我們只用一次遍歷，便可以求出目標(biāo)值。

遞歸算法的優(yōu)化大概就是避免重復(fù)運(yùn)算，將中金狀態(tài)保存起來，以便下次使用，從結(jié)構(gòu)上來看，是將時間復(fù)雜度轉(zhuǎn)換為空間復(fù)雜度來解決。遞歸算法的效率其實(shí)是非常低的，能不用遞歸就盡量不用遞歸；當(dāng)然了也要具體問題具體對待，比如說開始提到我做的項(xiàng)目遇到的問題，不用遞歸我還真想不出其他更好的方式解決。

作者：楊軼

來源：宜信技術(shù)學(xué)院