遍历未知层级嵌套文件目录的时间复杂度是多少？

你的结论只在部分日常场景下成立，严格来说全目录遍历的时间复杂度是O(总节点数)，总节点数=遍历范围内的所有目录数量+所有文件数量，推导逻辑如下： #

首先你可以把整个目录结构抽象成一棵无环多叉树：

• 遍历的起始目录是根节点
• 所有子目录是树的中间分支节点
• 所有普通文件是树的叶子节点

不管你用DFS（深度优先）还是BFS（广度优先）实现遍历，核心逻辑都是「访问当前节点→如果是目录就枚举它下面的所有子节点→递归/入队遍历子节点」，常规实现都会加已访问标记，避免符号链接/硬链接导致的死循环，整个流程里没有任何节点会被重复访问。
这里很容易忽略一个关键开销：哪怕你不在目录节点上做任何业务操作，你也必须为每个目录付出固定访问成本——你得先读取目录的条目列表，才能知道它下面有哪些子目录和文件，不然根本没法继续往下遍历。这个操作和你在文件节点上做的业务操作（比如读内容追加到目标文件）一样，每个目录恰好执行1次，是绕不开的必选步骤。 #

你最开始猜O(文件总数)是非常符合日常使用直觉的：绝大多数普通场景里，目录的数量远小于文件数量，比如普通用户的工作目录里，可能几千上万个文件才对应几百个目录，这时候目录数带来的开销只是常数系数级别的，大O表示法会忽略常数系数，所以O(目录数+文件数)看起来和O(文件数)几乎没有区别。
但这个结论不是普适的：举个极端反例，如果你有一个嵌套了10万层的空目录结构，里面一个文件都没有，这时候文件总数是0，但你遍历还是得依次访问这10万个目录，总耗时和目录数线性相关，这时候O(文件总数)的结论就完全不成立了。 #

最后补充两个特殊场景的复杂度变化：

• 如果你的遍历逻辑没有做环检测，碰到链接形成的环时会无限循环，这时候没有有界的时间复杂度，属于实现bug
• 如果你对每个文件的操作不是常数时间（比如要读取全文件内容计算哈希、做内容转码），那复杂度还要叠加所有文件的总大小带来的开销，这时候就不能单纯按节点数计算了。但如果只是你提到的文件追加类的元数据/句柄操作，每个节点的处理开销是常数，就符合前面说的O(总节点数)的结论。

内容的提问来源于stack exchange，提问作者TheRealFakeNews