瞭解樹型數據結構的運行時間

我有一個數據結構是一棵樹，其中每個父級可以有無限數量的子級，樹的最大深度爲4級。每個級別是不同的類。瞭解樹型數據結構的運行時間

我的朋友寫了一個算法遍歷這個由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）還是我的朋友O（n^3）？

來源

2012-11-08 Nicholas

你先生，是正確的。 – st0le

是的你是對的。你實際上僱用depth first search，它只訪問一次節點（即dfs的最壞情況），因此複雜度爲O（N）。就你的朋友而言，我不能理解他用n表示的深度（即是for循環的數量）這裏是固定的。

來源

2012-11-08 06:45:33

那麼，在圖的情況下，最大節點度對於_N_有更多的含義，但在這裏不是。 –

你說得對。訪問每個節點一次將使其成爲O（N），其中N是總數。樹中的節點。

來源

2012-11-08 06:34:57 srbhkmr

瞭解樹型數據結構的運行時間

回答

相關問題