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

Question

我有一个数据结构，它是一棵树，每个 parent 可以有无限数量的 child ，树的最大深度是 4。每一层都是一个不同的类。

我 friend 写了一个遍历这个由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)，或者我的 friend 是否正确，O(n^3)？

Answer 1

是的，你是对的。您实际上是在雇用 depth first search ，它只访问每个节点一次(即 dfs 的最坏情况)，因此复杂度为 O(N) 。就您的 friend 而言，我无法理解他用 n 表示的含义，因为深度(即 for 的数量循环)这里是固定的。