0

我编写了一个遍历非二叉树结构的递归算法。该结构由目录或文件组成。

该算法采用输入目录 ( curDirectory) 并首先遍历树深度。当它到达分支的底部时,它会查找文件并打印一些信息。然后它返回一个级别,查找文件并打印内容,等等。我们不知道目录中子目录或文件的数量。

如何分析该算法的最坏情况和平均情况时间?

for(int i = 0; i < curDirectory.getChildren().size(); i++){
        if (curDirectory.getChildren().get(i) instanceof INodeDirectory)
            blockCounter = blockCounter + digAndCount((INodeDirectory)curDirectory.getChildren().get(i));
    }

    for(int i = 0; i < curDirectory.getChildren().size(); i++){
        if (curDirectory.getChildren().get(i) instanceof INodeFile) {
            // print stuff and do other stuff 
        }
    }
4

1 回答 1

0

你的树有 N 个目录和 M 个文件。迭代时,每个目录和文件都会被处理一次。所以时间复杂度将是 O( M + N )。或者您可以决定处理目录和文件的时间大致相同,那么您可以说它的 O(N)。

树的结构无关紧要。如果您有一个非常深的目录和子目录树,或者一个非常浅的树,其中所有目录都是根的子目录 - 每个文件和每个目录都会被访问一次。

当您看到搜索树的算法时,例如平衡二叉树,其复杂性小于线性 - 这是因为它描述了对该树的搜索,该搜索不会访问每个节点。

于 2014-09-25T18:01:18.927 回答