algorithm - 查找构建二叉搜索树的时间复杂度

Question

假设我们有中序遍历order和后序遍历。例如:按顺序:30 40 45 50 65 70 80后序:30 45 40 65 80 70 50

我知道如何从给定的中序遍历和后序遍历构造二叉搜索树，但我的问题是如果给出后序遍历，B.S.T 构造的平均和最坏情况时间复杂度是多少？

Answer 1

在这两种情况下，对于朴素的 BST 构造算法，时间都是 O(n^2)，因为:

在有序的情况下，算法将添加到右边

在后序的情况下，算法将添加到左侧

所以 T(n) = 1 + 2 + 3 + ... n-1 = O(n^2)

UPDATE_3:但在后序情况下，我们可以简单地将每个下一个元素添加为根(前一棵树成为左儿子)，因此复杂度为 O(n)

更新:当然，数字排列的平均时间是 O(n logn)，但在那些情况下，这次时间是 O(n^2)(n 是数字的数量)

UPDATE_2:有关更多详细信息，请查看底部的评论。