c# - 一个简单的代码顺序

Question

今天我和我的老板讨论了我的代码的顺序，但我们无法就我的代码的时间复杂度达成一致。我相信我的代码是O(n)，但我的老板不接受。

您对这段代码的顺序有何看法？

void Process(Node currentNode)
{
    Print(currentNode.Title); //O(Print)=O(1)
    foreach(Child child in currentNode.Children)
    {
        Process(child);
    }
}

---

编辑1

多个 Node 不共享同一个子 Node。我有一棵树。Children 是一个简单的 Node 列表，因此可以在线性时间内轻松访问其成员。

你可以在这里看到 Node 类的实现:

class Node
{
    public string Title{get;set;}
    public List<Node> Children{get;set}
}

Answer 1

如果这是 a tree n 是树中的节点数...

那么是的，它是 O(n)。

很容易看出我们每个节点只做恒定量的工作。

每个节点只会是另一个节点的子节点，因此它只会出现在 for 循环中一次。由于 for 循环迭代(不包括递归调用)采用 O(1)，我们可以看到递归的 for 循环部分(对于所有调用)采用 O (n)。函数的其余部分显然是 O(1)，并且从树的定义中，我们可以看到每个节点只执行一次函数，因此 O( n) 次。

因此总的运行时间是O(n)。

注意:我假设 Children 是可以在线性时间内枚举的东西。如果不是这样，运行时间将与枚举它所花费的时间相同。更具体地说，最坏的情况是一个节点将剩余的 n-1 节点作为子节点(并且其他节点都没有子节点)。我认为证明这一点会分散注意力，所以我改天再说。

---

如果它不是一棵树，即多个节点可以有相同的 child ，或者有一个循环，它不是O(n)。在循环的情况下，它不会终止。如果多个节点可以有相同的子节点，但没有循环，则运行时间将呈指数增长 - 根节点可以有 n-1 个子节点。其中一个 child 可以有 n-2 个 child ，其中一个可以有 n-3 个 child ，等等。