简单代码的顺序

Question

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

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

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

---

EDIT1

多个Nodes不共享同一个孩子Node.我有一棵树. Children是一个简单的列表,Node以便其成员可以在班轮时间轻松访问.

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

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

Answer 1

如果这是一棵树并且n是树中的节点数...

是的,是的O(n).

很容易看出我们每个节点只进行一定量的工作.

每个节点只是一个子节点到另一个节点,因此它只出现在for循环中一次.并且由于不包括递归调用的for循环迭代,O(1)我们可以看到递归的for循环部分(对于所有调用)都接受了O(n).并且函数的其余部分清楚O(1),并且,从树的定义,我们可以看到我们每个节点只执行一次函数,因此O(n)时间.

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

注意:我假设Children是可以在线性时间内枚举的东西.如果不是这样,则运行时间与枚举它所需的时间相同.更具体地说,最坏的情况是当一个节点将剩余n-1节点作为子节点(并且其他节点都没有子节点)时.我认为这样做的证据会分散注意力,所以我会把它留给另一天.

如果它不是树,即多个节点可以有相同的子节点,或者存在循环,则不是O(n).在循环的情况下,它不会终止.如果多个节点可以拥有相同的子节点,但没有一个循环,则运行时间将是指数级的 - 根节点可以有n-1子节点.其中一个孩子可以生n-2孩子,其中一个可以生n-3孩子等.