问题描述
我必须计算算法的时间复杂度，但在其中我调用了 os.walk，我不能将其视为单个操作，而是多个操作.
I've to calculate the time-complexity of an algorithm, but in it I'm calling os.walk which I can't consider as a single operation but many.
os.walk 的来源让我感到困惑，因为文件树可能以多种方式排序(文件夹中有 1.000.000 个文件或每个文件夹和 1.000.000 个文件夹.
The sources of os.walk left me confused as the filetree may be ordered in many ways (1.000.000 files in a folder or a file per folder and 1.000.000 folders.
我不是时间复杂性方面的专家，我不能确定我应该只考虑一个操作还是多个操作，所以这让我陷入困境.不要计算 simlink 标志，我假设将其设置为 false 以忽略它们.
I'm not an expert on time-complexities, I can't be sure on what I should consider as only an operation or many, so this left me stuck. Don't count the simlink flag, which I assume set to false to ignore them.
PD:我在 Komodo IDE 中找到了 os.walk 的源代码，但我不知道如何在 javadoc 中找到它们.
PD: I found the sources of os.walk in the Komodo IDE, but I wouldn't know how to find them as the javadocs.
推荐答案
好吧...让我们来看看源代码 :)
Well... let's walk through the source :)
文档:http://docs.python.org/2/图书馆/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 是文件/目录的总数在给定的路径中.
Since it's a generator it all depends on how far you walk the tree, but it looks like O(n) where n is the total number of files/directories in the given path.
这篇关于Python 中 os.walk 的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！