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

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

很难精确计算，但看起来在最坏的情况下它不是多项式有界的（但这不是一个完整的证明，你需要一个更好的证明）：

insert 在最坏的情况下具有复杂度 O(h)，其中 h 是树的高度（即至少 log(n)，可能 n） .
merge() 的复杂性可以是以下形式：T(n1, n2) = O(h) + T(n1 / 2, n1 / 2) + T(n1 - 1, n2)
让我们考虑 F(n) 这样 F(1)=T(1, 1) 和 F(n+1)=log(n)+F(n/2)+F(n-1)。我们可能可以证明 F(n) 小于 T(n, n)（因为 F(n+1) 包含 T(n, n) 而不是 T(n, n+1)）。
我们有F(n)/F(n-1) = log(n)/F(n-1) + F(n/2) / F(n-1) + 1
假设 F(n)=Theta(n^k) 一些 k。然后 F(n/2) / F(n-1) >= a / 2^k 对于一些 a>0 （来自 Theta 中的常量）。
这意味着（超过某个点n0）对于某些固定的epsilon > 0，我们总是有F(n) / F(n-1) >= 1 + epsilon，这与[=32=不兼容]，因此矛盾。
所以 F(n) 不是任何 k 的 Theta(n^k)。直觉上，您可以看到问题可能不是 Omega 部分，而是 big-O 部分，因此它可能不是 O(n) （但从技术上讲，我们在这里使用了 Omega 部分得到 a)。由于 T(n, n) 应该比 F(n) 更大，T(n, n) 不应该是多项式的 ，并且可能是指数的...

不过话又说回来，这一点都不严谨，所以也许我真的错了...

Answer 2

让我们考虑最坏的情况：

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 直接引用的内容。如您所见，这背后的基本思想很简单，尽管代数非常乏味。

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

Time complexity of naïve merge of two binary search trees

algorithm

merge

time-complexity

binary-search-tree

asymptotic-complexity