遍歷非二叉樹的最壞情況

我寫了一個遍歷非二叉樹結構的遞歸算法。該結構由目錄或文件組成。遍歷非二叉樹的最壞情況

算法採用輸入目錄（curDirectory）並首先遍歷樹的深度。當它到達分支的底部時，它會查找文件並打印一些信息。然後它返回一個級別，查找文件和打印內容等等。我們不知道目錄中的子目錄或文件的數量。

如何分析此算法的最差情況和平均情況時間？

for(int i = 0; i < curDirectory.getChildren().size(); i++){ 
     if (curDirectory.getChildren().get(i) instanceof INodeDirectory) 
      blockCounter = blockCounter + digAndCount((INodeDirectory)curDirectory.getChildren().get(i)); 
    } 

    for(int i = 0; i < curDirectory.getChildren().size(); i++){ 
     if (curDirectory.getChildren().get(i) instanceof INodeFile) { 
      // print stuff and do other stuff 
     } 
    }

來源

2014-09-25 Simon Carlson

最好的和最差的關於什麼？ – 2014-09-25 17:25:15

時間複雜度，將其添加到我的問題。 – 2014-09-25 17:26:14

是的，但關於什麼時間複雜？文件數量？目錄數量？還有別的嗎？ – 2014-09-25 17:27:01

你的樹有N個目錄和M個文件。迭代時，每個目錄和文件將被處理一次。所以時間複雜度將是O（M + N）。或者你可以決定處理目錄和文件的時間大致相同，那麼你可以說它的O（N）。

樹的結構並不重要。如果你有一個非常深的目錄和子目錄樹，或者是一棵很淺的樹，其中所有的目錄都是根目錄的子目錄 - 每一個文件和每個目錄都會被訪問一次。

當您看到搜索樹（比如平衡二叉樹）的複雜性小於線性的算法時 - 它是因爲其描述了對該樹沒有訪問每個節點的搜索。

來源

2014-09-25 18:01:18

遍歷非二叉樹的最壞情況

回答

相關問題