我看到了一个非常短的算法来合并两个二叉搜索树 . 我很惊讶它是多么简单而且非常低效 . 但当我试图猜测它的时间复杂性时,我失败了 .
让我们有两个不可变的二进制搜索树(不 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 回答
让我们考虑最坏的情况:
在这种极端情况下,
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)
.笔记:
参数的顺序很重要 . 因此,通常将较小的树插入较大的树中(以说话的方式) .
实际上,你不太可能在手术的每个阶段都有最大不 balancer 的树木 . 平均情况下自然会涉及半 balancer 树木 .
最佳情况(即总是完全 balancer 的树)要复杂得多(我不确定存在如上所述的分析解决方案;请参阅
gdelab
的回答) .编辑:如何评估指数和
假设我们想要计算总和:
其中
a, b, c, n
是正常数 . 在第二步中,我们将基数更改为e
(自然指数常数) . 通过这种替换,我们可以将ln c
视为变量x
,区分几何级数,然后设置x = ln c
:但是几何级数有一个封闭形式的解决方案(标准公式并不难推出):
因此,我们可以将此结果与
x
区分n
次,以获得Sn
的表达式 . 对于上面的问题,我们只需要前两个权力:因此,麻烦的术语由下式给出:
这正是Wolfram Alpha直接引用的内容 . 正如您所看到的,这背后的基本思想很简单,尽管代数非常繁琐 .
这很难精确计算,但看起来它在最坏的情况下不是多项式限制的(这不是一个完整的证明,但是你需要一个更好的证明):
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)
不应该是多项式的,并且可能是指数的......但话说回来,这根本不严谨,所以也许我真的错了......