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

Question

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

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

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

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

Answer 1

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

文档: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 是文件/目录的总数在给定的路径中。