algorithm - 如果我们可以在融合树中以恒定时间计算草图（x）怎么办？

Question

我知道在融合树中不可能在恒定时间内找到sketch(x)，这就是我们计算ApproxSketch(x)的原因。但是，我很想知道如果可以在constant time中计算sketch(x) ，搜索时间会受到怎样的影响。

标签： algorithmdata-structurestreetime-complexityfusion

Answer 1

它会下降一个恒定的因素。

树的分支因子会从 Θ(w ^1/5 ) 到 w+1。树的高度为 O(log _b n) = O(log n/log b) 其中 b 是分支因子，b 从 (1/5) log w + Θ(1) 变为 log (w+1 ）。