0

我有一个算法可以搜索一个目录并搜索该目录和任何子目录中的所有文本文件。假设我不知道父目录中有多少子目录和子目录。我如何计算复杂度？

这是我正在使用的代码

 public List<string> GetFilesInDirectory(string directoryPath)
    {            
        // Store results in the file results list.
        List<string> files = new List<string>();

        // Store a stack of our directories.
        Stack<string> stack = new Stack<string>();

        // Add initial directory.
        stack.Push(Server.MapPath(directoryPath));

        // Continue while there are directories to process
        while (stack.Count > 0)
        {                
            // Get top directory
            string dir = stack.Pop();

            try
            {             
                // Add all files at this directory to the result List.
                files.AddRange(Directory.GetFiles(dir, "*.txt"));                    

                // Add all directories at this directory.
                foreach (string dn in Directory.GetDirectories(dir))
                {
                    stack.Push(dn);
                }
            }
            catch(Exception ex)
            {

            }
        }

        return files;
    }

谢谢

4

6 回答 6

3

Big-O 表示法说明了当参数大小增加时问题复杂性如何增加。换句话说，当元素集增加时，时间复杂度如何增加。1 或 8972348932 个文件/目录无关紧要。您的代码在 O(N) 线性时间内工作，假设目录和文件只被访问一次。O(123N) 仍然写为 O(N)。这是什么意思？这意味着大 O 表示法没有说明实际的初始成本。只有复杂性如何增长。

比较同一问题的两种算法，它们在 O(N) 时间和 O(N log N) 时间内运行。对于较小的 N，O(N log N) 算法可能比 O(N) 算法更快，但如果 N 足够大，O(N) 会赶上。

于 2009-11-29T22:03:33.683 回答
1

我会说所有目录中的文件数量是 O(N)。

浏览这些目录并不是一项复杂的任务，它只是簿记。

于 2009-11-29T21:46:53.500 回答
1

您的算法将所有目录推送到您的堆栈上并对其遇到的每个目录都有效，因此复杂性按目录乘以 2 的顺序，或 O(2n) 其中 n 是目录数，就复杂性而言，这是相当于 O(n)。

于 2009-11-29T21:50:17.037 回答
0

我会说它是 O(N^2) 因为你有一个双嵌套的 for 循环，但是每个循环的大小不一样，所以我们必须稍微修改一下。

目录的数量可能小于文件的数量。因此，假设文件数为 N，目录数为 M，那么您将得到 O(N*M)。这是我最好的猜测。

于 2009-11-29T22:53:14.070 回答
0

时间复杂度是根据 计算的n，其中n是正在处理的项目数。您不需要精确的数字，更重要的是，您不能使用精确的数字来计算大 O 复杂性，因为您正在尝试计算最坏情况下的运行时间。

于 2009-11-29T21:46:39.067 回答
0

最坏的情况下运行时间是目录树的最大深度（在 Windows 中受最大路径长度限制）和子目录中允许的文件数的函数

于 2009-11-29T21:49:11.590 回答