樹恢復程序的遞歸運行時間

我想弄清楚我已經提出的遞歸算法的運行時間。給定preOrder和inOrder遍歷樹的算法找到postOrder遍歷。這裏是我的算法：樹恢復程序的遞歸運行時間

Recovery(preOrder, inOrder): 
    root = preOrder[0] 
    rootIndex = inOrder.find(root) 

    if preOrder.length <= 0 
     return; 

    leftPreord = preOrder[1...rootIndex] 
    leftInord = inOrder[0...rootIndex] 
    rightPreord = preOrder[rootIndex + 1 ... End] 
    rightInord = inOrder[rootIndex + 1 ... End] 

    Recovery(leftPreord, leftInord) 
    Recovery(rightPreord, rightInord) 

    print preOrder[0]

我的問題是，如果該算法基本上具有相同的運行時間作爲歸併算法，O（nlogn）。

該算法的非遞歸部分（主要是.find（）運算符）在O（n）時間運行，然後兩個遞歸調用運行在T（n/2）時間。因此，T（n）= T（n/2）+ O（n）。樹的高度是log n，每個級別運行n次，因此O（nlogn）。我唯一擔心的是，對於每次遞歸調用，它在技術上都是T（（n-1）/ 2），因爲我們將當前的根留下。這是否有所作爲？

來源

2016-02-16 mjones

你的邏輯是健全的。每次迭代的步驟由O（1）和O（n）運算的和組成。這些總和就是任何步驟的最高階數：O（n）。你有log（n）[base2]級別，這確實給你一個算法O（n log n）。

好推理。

來源

2016-02-16 00:58:54 Prune

樹恢復程序的遞歸運行時間

回答

相關問題