证明一棵树的树遍历算法的时间复杂度

我正在寻找一种方法来证明一棵n-tree树的树前遍历算法的运行时间。证明一棵树的树遍历算法的时间复杂度

每个节点可以有任意数量的子节点。

我似乎只能找到二叉树的证明。

我直观地理解运行时间将是O（n），但是对于如何提出严格的证明感到困惑。

在预先遍历的节点v上完成的工作是O（1 + c_v），其中c_v是节点v的子节点数，这是因为我们做了一些恒定的工作量，然后准确地访问每个子节点一旦。

在所有节点上总结这个结果给出了O（n）加上所有节点上的O（c_v）之和v。这个数量是O（n），因为跨越每个树节点的子节点数相等于总结所有节点，但根（你明白为什么？）

总的来说，运行时间是O（n）。

希望这会有所帮助！

2014-09-18 17:57:54 templatetypedef

我知道时间是O（n），毕竟算法的目的是访问每个节点一次。我想知道是否有更正式的方法来证明它。 – user2059807 2014-09-19 02:17:08

我认为这已经足够正式了 - 如果一个学生在算法课上把它变成了，我会给它充分的信任。 :-) – templatetypedef 2014-09-19 04:07:56

回答