首页 文章

两个二叉搜索树的幼稚合并的时间复杂性

提问于
浏览
2

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

让我们有两个不可变的二进制搜索树(不 balancer ),它包含整数,你想用伪代码中的下面的递归算法将它们合并在一起 . 函数 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)

我猜它是一个exponencial算法,但我无法找到一个参数 . 这种合并算法的最差时间复杂度是多少?

2 回答

  • 0

    让我们考虑最坏的情况:

    在每个阶段,每个树处于最大不 balancer 状态,即每个节点具有至少一个大小为1的子树 .

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


    基于上述约束,我们可以推导出 merge 的时间复杂度的递归关系:

    enter image description here

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

    • T(n - 2, 1) :在 t1 的子树上内部调用 merge

    • T(n - 1, m) :在 t2 上外部调用 merge

    • Ө(n + m) :最后一次致电 insert


    为了解决这个问题,让我们重新替换第一个术语并观察一个模式:

    enter image description here

    我们可以通过剥离第一个术语来解决这个问题:

    enter image description here

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

    enter image description here

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

    因此合并的绝对最坏情况时间复杂度是


    笔记:

    • 参数的顺序很重要 . 因此,通常将较小的树插入较大的树中(以说话的方式) .

    • 实际上,你不太可能在手术的每个阶段都有最大不 balancer 的树木 . 平均情况下自然会涉及半 balancer 树木 .

    • 最佳情况(即总是完全 balancer 的树)要复杂得多(我不确定存在如上所述的分析解决方案;请参阅 gdelab 的回答) .


    编辑:如何评估指数和

    假设我们想要计算总和:

    enter image description here

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

    enter image description here

    但是几何级数有一个封闭形式的解决方案(标准公式并不难推出):

    enter image description here

    因此,我们可以将此结果与 x 区分 n 次,以获得 Sn 的表达式 . 对于上面的问题,我们只需要前两个权力:

    enter image description here

    因此,麻烦的术语由下式给出:

    enter image description here

    这正是Wolfram Alpha直接引用的内容 . 正如您所看到的,这背后的基本思想很简单,尽管代数非常繁琐 .

  • 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 )我们总是有 F(n) / F(n-1) >= 1 + epsilon 用于某些固定的 epsilon > 0 ,这与 F(n)=O(n^k) 不兼容,因此是矛盾的 .

    • 所以 F(n) 对于任何 k 都不是 Theta(n^k) . 直觉上,您可以看到问题可能不是 Omega 部分而是 big-O 部分,因此它可能不是 O(n) (但从技术上讲,我们在这里使用 Omega 部分得到 a ) . 由于 T(n, n) 应该比 F(n) 更大, T(n, n) 不应该是多项式的,并且可能是指数的......

    但话说回来,这根本不严谨,所以也许我真的错了......

相关问题