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

Question

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

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（我们需要搜索的目录路径）。在此函数中，我递归地在父目录及其所有子目录中搜索具有给定扩展名的文件。我将所有这些具有给定后缀的文件存储在列表中并返回它。

时间和Space复杂度：

时间复杂度：

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

的长度

path_elements = os.listdir(path)

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

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

同样，遍历 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是depth中每个级别的目录数（branches）那么递归将需要O(brancher^depth) => O(k^depth).但是对于每个递归调用，都会执行以上三个步骤。因此，总时间复杂度为O((k^depth) * e

Space 复杂度：

输入Space
- 后缀 - O(1)
- 路径 - O(1)
- path_elements + path_files + path_folders => O(e + f + g) => O(e)
辅助Space

递归使用一种叫做"call stack"的东西。当函数调用自身时，该函数位于堆栈顶部。
- 在这个算法中，递归函数只有遍历每一个目录才算穷尽。也就是说，当它已经达到了depth。因此调用堆栈中需要 O(depth) space。
总Space复杂度=>输入Space+辅助Space=>O(e + depth)

Answer 1

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

folder
  zip.c
  foo.c
  bar.c
  bas.c

因此您的函数调用 os.listdir()，其中 returns 四个文件。所以n = 4。然后，代码遍历列表以查找文件夹，找到 none，然后再次挑选出 .c 文件，并将其添加到列表中。

这里的复杂度是 O(n) 来调用 os.listdir()，O(n) 来搜索文件夹，O(n) 来挑选 .c 文件并将它们添加到列表中。总共O(3*n)，也就是O(n).

现在考虑这个目录树：

folder
  sub1
    zip.c
    foo.c
  sub2
    bar.c
    bas.c

所以第一个调用find_files调用os.listdir(folder)，其中returns两个文件夹。每个文件夹递归调用 find_files。一共调用了 3 次 os.listdir()，每次 returns 两个文件，所以 os.listdir() 返回的项目总数是 6。

现在假设您有：

folder
  sub0
    sub1
      sub2
        sub3
          ...
            sub30
              file1.c

这里的复杂度还是O(n)。在本例中，n 为 31。

我在这里想表达的意思是，您查看从 os.listdir() 返回的每个项目的次数是恒定的。因此，O(n).

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

Time and space complexity of a File Recursion algorithm

python

algorithm

recursion

time-complexity

space-complexity

解释：文件递归