文件递归算法的时间和空间复杂度

Question

我的时间和空间分析对这个算法正确吗？

def find_files(suffix, path):
if suffix == '':
    return []

# Base condition
if len(os.listdir(path)) == 0:
    return []

path_elements = os.listdir(path)
path_files = [file for file in path_elements if ('.' + suffix) in file]
path_folders = [folder for folder in path_elements if '.' not in folder]

for folder in path_folders:
    path_files.extend(find_files(suffix=suffix, path=path + '/' + folder))

return path_files

# Tests
path_base = os.getcwd() + '/testdir'
print(find_files(suffix='c', path=path_base))

说明：文件递归

需求：

目标是编写代码以查找目录下所有以“ .c”结尾的文件（及其下所有目录）

摘要：

为了实现这一点，我使用了find_files函数，该函数将使用suffix（文件扩展名）和path（我们需要搜索的目录路径）。在此功能中，我在父目录及其所有子目录中递归搜索具有给定扩展名的文件。我将所有具有给定后缀的文件存储在列表中并返回。

时空复杂度：

时间复杂度：

os.listdir（path）将列出给定路径中的所有文件和文件夹。由于必须迭代每个项目才能提供列表，因此需要线性时间复杂度。令e为path_elements的长度=>O(len(path_elements))=> O(e)

path_elements = os.listdir(path)

2. 下一行将通过检查文件名中是否存在.c来找出给定路径中的所有文件。如果s是字符串的长度（文件/文件夹的名称），则需要O(s)时间才能找到具有给定扩展名的文件。因此，对于f个文件，需要O(f*s)时间。出于这样的实际目的，可以公平地假设文件名不是无限长。因此，我们可以假设s为常数=>O(f * 1)=> O(f)。

path_files = [file for file in path_elements if ('.' + suffix) in file]

3. 类似地，遍历g目录将花费线性时间=> O(g)

path_folders = [folder for folder in path_elements if '.' not in folder]

以上3个步骤将采取=>O(e + f + g)=> O(e)。由于e（len(path_elements)）是主要术语，因为它是path_files和path_folders的组合。

• 对于递归，如果k是branches中每个级别的目录数（depth），则递归将采用O(brancher^depth) => O(k^depth)。但是，对于每个递归调用，都执行上述三个步骤。因此，总时间复杂度为O((k^depth) * e

空间复杂度：

1. 输入空格

   • 后缀-O(1)
   • 路径-O(1)
   • 路径元素+路径文件+路径文件夹=>O(e + f + g)=> O(e)

2. 辅助空间

递归使用称为“调用堆栈”的东西。当一个函数调用自身时，该函数将进入堆栈的顶部。

• 在此算法中，仅当递归函数遍历每个目录时，它才被用尽。换句话说，到达depth时。因此，调用堆栈中需要O(depth)空间。

总空间复杂度=>输入空间+辅助空间=> O(e + depth)

我的时间和空间分析对这种算法是否正确？ def find_files（suffix，path）：if suffix ==''：return []＃基本条件，如果len（os.listdir（path））== 0：返回[] path_elements = ...

Answer 1

我认为复杂度为O（path_elements），其中path_elements是所有对os.listdir()的调用返回的文件和文件夹的总数。考虑一个在单个目录中具有四个文件的文件夹：