algorithm - 了解树型数据结构的运行时间

Question

我有一个数据结构是一棵树，其中每个父级可以有无限数量的子级，树的最大深度是 4。每个级别都是一个不同的类。

我的朋友写了一个算法来遍历这个由 for 循环组成的，伪代码如下：

root = tree.root();
for (int i = 0; i < root.children_size(); i++)
    child1 = root.child(i);
    for(int j = 0; j < child1.children_size(); j++)
        child2 = child1.child(j);
        for(int k = 0; k < child2.children_size(); k++)
            child3 = child2.child(k);

他声称因为它有 3 个 for 循环，所以该算法的运行时间是 O(n3)。当我问他 n 是什么时，他说是 for 循环的数量，这没有意义，因为 n 必须是这棵树中的一个结构。我声称 n 是树中总节点的数量，该算法的运行时间为 O(n)，因为运行时间将为 O(root.children_size + child1.children_size + child2.children_size)。

我对运行时间的假设是正确的，O(n)，还是我的朋友，O(n^3)？

Answer 1

是的你是对的 。您实际上是在使用深度优先搜索，它只访问每个节点一次（即 dfs 的最坏情况），因此复杂度为 O(N)。就您的朋友而言，我无法理解他用 n 表示什么，因为深度（即for循环的数量）这里是固定的。

Answer 2

你说的对。访问每个节点一次将使其 O(N)，其中 N 是总数。树中的节点数。