證明一棵樹的樹遍歷算法的時間複雜度

我正在尋找一種方法來證明一棵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

回答