树恢复程序的递归运行时

Question

我正在尝试找出我提出的递归算法的运行时间。给定树的 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]

我的问题是这个算法是否基本上与 MergeSort 算法具有相同的运行时间，O(nlogn)。

算法的非递归部分（主要是.find()算子）运行s在O(n)时间，然后两次递归调用运行在T(n/2) 时间。因此，T(n) = T(n/2) + O(n)。树的高度是 log n，每个级别运行s 在 n 时间内，因此 O(nlogn)。我唯一担心的是，对于每个递归调用，它在技术上都是 T((n-1)/2) 因为我们将当前根留在后面。这有什么区别吗？

Answer 1

你的逻辑很有道理。每次迭代的步骤由 O(1) 和 O(n) 操作的总和组成。这些的总和只是任何步骤的最高阶：O(n)。您有 log(n) [base2] 级别，这确实会给您留下 O(n log n) 的算法。

推理很好。

树恢复程序的递归运行时

Recursive Runtime of Tree Recovery Program

c++

algorithm

recursion

runtime

analysis