树恢复程序的递归运行时间

我想弄清楚我已经提出的递归算法的运行时间。给定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

树恢复程序的递归运行时间

回答

相关问题