0

如何计算以下函数的时间和空间复杂度。我已经尝试过，但由于递归函数调用而感到困惑。

public void readDirectory(File file){
    if(file.isDirectory()){
        File[] folder = file.listFiles();
        for (File f : folder) {
            readDirectory(f);
        }
    }else{
        if(file.getName().contains("(2)"))
            System.out.println(file.getName());
    }
}
4

2 回答 2

1

时间 = O(n)

  • 对于文件夹层次结构的每个级别，您for只为该级别的项目执行循环。如果文件系统中共有n项目（文件和文件夹），则每个文件夹中只有该数量的一部分，每个文件夹中的所有项目总和为n. 在递归的每个级别，您都对该级别进行线性遍历并为每个孩子调用该函数。在为每个级别执行之后，您仍然有线性时间，因为对于您在线性时间中遍历的每个级别，只有所有文件的细分和所有细分的总和文件总数。

空间 = O(n)

  • 同样，您具有O(n)空间复杂性，因为您为当前路径中的每个文件/文件夹分配了一个File对象。它实际上等于文件夹层次结构的最大深度，因为您将File对象保留在每一级，直到下一级递归调用完成，但只有在那之后才释放它们。在最坏的情况下，文件夹层次结构可能O(n)很深 - 当每个子文件夹中只有 1 个子文件夹且没有文件时。这给你一个O(n)空间复杂性
于 2013-09-12T12:35:50.393 回答
-1

这是一个 DFS。folder时间复杂度为 O(n) （您访问每个文件一次）变量的空间为 O(max{|directory|}) 。

于 2013-09-12T11:58:52.090 回答