包含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循环的递归函数的时间复杂度

回答

相关问题