algorithm - 两个二叉搜索树的简单合并的时间复杂度

Question

我看到了一个非常简短的合并两个二叉搜索树的算法。我很惊讶它是多么容易，而且效率很低。但是当我试图猜测它的时间复杂度时，我失败了。

让我们有两个包含整数的不可变二叉搜索树(不平衡)，您希望使用以下伪代码中的递归算法将它们合并在一起。函数insert辅助:

function insert(Tree t, int elem) returns Tree:
    if elem < t.elem:
        return new Tree(t.elem, insert(t.leftSubtree, elem), t.rightSubtree)
    elseif elem > t.elem:
        return new Tree(t.elem, t.leftSubtree, insert(t.rightSubtree, elem))
    else
        return t

function merge(Tree t1, Tree t2) returns Tree:
    if t1 or t2 is Empty:
        return chooseNonEmpty(t1, t2)
    else
        return insert(merge(merge(t1.leftSubtree, t1.rightSubtree), t2), t1.elem)

我猜它是一个指数算法，但我找不到它的论据。该合并算法的最差时间复杂度是多少？

Answer 1

让我们考虑最坏的情况:

At each stage every tree is in the maximally imbalanced state, i.e. each node has at least one sub-tree of size 1.

在这种极端情况下，insert 的复杂度很容易显示为 Ө(n) 其中 n 是元素的数量树，因为高度是 ~ n/2。

---

根据上述约束，我们可以推导出merge时间复杂度的递归关系:

其中 n, m 是 t1, t2 的大小。不失一般性地假设右子树总是包含单个元素。术语对应于:

• T(n - 2, 1):在 t1
的子树上对 merge 的内部调用
• T(n - 1, m):在 t2
上对 merge 的外部调用
• Ө(n + m):最后调用insert

---

为了解决这个问题，让我们重新代入第一项并观察一个模式:

我们可以通过去掉第一项来求解这个和:

在步骤 (*) 中，我们使用了变量替换 i -> i + 1。当 k = n 时递归停止:

T(1, m)只是将一个元素插入到一棵大小为m的树中，显然是Ө(m) 在我们假定的设置中。

Therefore the absolute worst-case time complexity of merge is

---

注意事项:

• 参数的顺序很重要。因此，将较小的树插入较大的树(以某种方式来说)是很常见的。
• 实际上，您极不可能在过程的每个阶段都出现最大不平衡树。一般情况下自然会涉及半平衡树。
• 最佳 情况(即总是完全平衡的树)要复杂得多(我不确定是否存在像上面这样的分析解决方案；请参阅 gdelab 的回答) .

---

编辑:如何计算指数和

假设我们要计算总和:

其中 a、b、c、n 是正常数。在第二步中，我们将基数更改为 e(自然 指数常数)。通过这种替换，我们可以将 ln c 视为变量 x，根据它区分一个几何级数，然后设置 x = ln c:

但是几何级数有一个闭式解(一个不难推导的标准公式):

因此我们可以将此结果关于 x 微分 n 次以获得 Sn 的表达式。对于上面的问题，我们只需要前两个幂:

所以这个麻烦的术语是:

这正是 Wolfram Alpha 直接引用的内容。如您所见，这背后的基本思想很简单，尽管代数非常乏味。