包含for循環的遞歸函數的時間複雜度

-5

該函數的時間複雜度（O）是多少？我在我的代碼中也合併了二進制搜索。我知道二分查找是O（log n），mergesort是O（nlogn），但是這個算法的複雜度是多少？包含for循環的遞歸函數的時間複雜度

import os 

mydatafile = open("myss.csv","w+") 
def rec(searchpath): 
    if os.path.isdir(searchpath): 
     for i in os.listdir(searchpath): 
      childpath = os.path.join(searchpath,i) 
      if not os.path.isdir(childpath): 
       mydata = i + ", " + childpath + "\n" 
       mydatafile.write(mydata) 
      else: 
       mydata = i + ", " + childpath + "\n" 
       mydatafile.write(mydata) 
       rec(childpath) 
rec("C:\Python27") 
mydatafile.close()

來源

2016-09-19 Muhammad Salman Abbasi

http://stackoverflow.com/questions/2709106/time-complexity-of-a-recursive-algorithm – dwbartz

I/O函數有點掩蓋輸入。您可能認爲根目錄searchpath的名稱是輸入，但將輸入視爲表示目錄層次結構的根樹是更合理的。假設（再次，合理地）在每個節點完成了一個恆定的工作量，運行時間就是O（n）。

來源

2016-09-19 18:07:52 chepner

因此，這意味着我的整個代碼的時間複雜度將是nlogn，因爲我還有mergesort和binarysearch？ –

這取決於您正在排序和搜索的內容。如果您對結果數據文件進行一次排序（或者最多不變的次數），那仍然是O（n lg n）。每個二進制搜索都是O（lg n），所以如果你進行'k'搜索（其中'k'和'n'是獨立的），你最終會得到O（n lg n + k lg n）。（基本上說，總的運行時間是有限的，無論哪個更長，排序或搜索。） – chepner

包含for循環的遞歸函數的時間複雜度

回答

相關問題