python之Python 中 os.walk 的时间复杂度

我必须计算算法的时间复杂度，但在其中调用 os.walk，我不能将其视为单个操作，而是多个操作。

os.walk 的来源让我感到困惑，因为文件树可能以多种方式排序(一个文件夹中有 1.000.000 个文件或每个文件夹一个文件和 1.000.000 个文件夹。

我不是时间复杂性方面的专家，我不能确定我应该将什么仅视为一个操作或多个操作，所以这让我陷入困境。不要计算 simlink 标志，我假设将其设置为 false 以忽略它们。

PD:我在 Komodo IDE 中找到了 os.walk 的源代码，但我不知道如何找到它们作为 javadocs。

请您参考如下方法:

好吧...让我们浏览一下源代码:)

文档:http://docs.python.org/2/library/os.html#os.walk

def walk(top, topdown=True, onerror=None, followlinks=False): 
    islink, join, isdir = path.islink, path.join, path.isdir 
 
    try: 
        # Note that listdir and error are globals in this module due 
        # to earlier import-*. 
 
 
        # Should be O(1) since it's probably just reading your filesystem journal 
        names = listdir(top) 
    except error, err: 
        if onerror is not None: 
            onerror(err) 
        return 
 
    dirs, nondirs = [], [] 
 
 
    # O(n) where n = number of files in the directory 
    for name in names: 
        if isdir(join(top, name)): 
            dirs.append(name) 
        else: 
            nondirs.append(name) 
 
    if topdown: 
        yield top, dirs, nondirs 
 
    # Again O(n), where n = number of directories in the directory 
    for name in dirs: 
        new_path = join(top, name) 
        if followlinks or not islink(new_path): 
 
            # Generator so besides the recursive `walk()` call, no additional cost here. 
            for x in walk(new_path, topdown, onerror, followlinks): 
                yield x 
    if not topdown: 
        yield top, dirs, nondirs 

因为它是一个生成器，所以它完全取决于你在树上走多远，但它看起来像 O(n)，其中 n 是文件/目录的总数在给定的路径中。