0

我试图解决如何在给定的数组和两个索引中找到 O(Log(n)) 中这两个索引之间的最小值。我看到了使用段树的解决方案，但不明白为什么这个解决方案的时间复杂度是 O(Logn)，因为它看起来不像这样，因为如果你的范围不完全在节点的范围内，你需要开始拆分搜索。

4

1 回答 1

1

第一个证明：

声称在每个级别上最多扩展 2 个节点。我们将通过反证法来证明这一点。

考虑下面给出的线段树。

在此处输入图像描述

假设在这棵树中展开了 3 个节点。这意味着范围是从最左边的彩色节点到最右边的彩色节点。但请注意，如果范围延伸到最右边的节点，则覆盖中间节点的整个范围。因此，该节点将立即返回该值并且不会被扩展。因此，我们证明在每个级别上，我们最多扩展 2 个节点，并且由于存在 logn 级别，因此扩展的节点是 2⋅logn=Θ(logn)。

资源

第二个证明：

查询区间(x,y)有四种情况

FIND(R,x,y) //R is the node
% Case 1
    if R.first = x and R.last = y   
        return {R}
% Case 2
    if y <= R.middle
        return FIND(R.leftChild, x, y) 
% Case 3
    if x >= R.middle + 1 
        return FIND(R.rightChild, x, y) 
% Case 4
    P = FIND(R.leftChild, x, R.middle)
    Q = FIND(R.rightChild, R.middle + 1, y)    
    return P union Q.

直观地说，前三种情况将树高级别降低 1，因为树的高度为 log n，如果只发生前三种情况，则运行时间为 O(log n)。

对于最后一种情况，FIND() 将问题分成两个子问题。但是，我们断言这最多只能发生一次。在我们调用 FIND(R.leftChild, x, R.middle) 之后，我们正在查询 R.leftChild 的区间 [x, R.middle]。R.middle 与 R.leftChild.last 相同。如果 x > R.leftChild.middle，则为案例 1；如果 x <= R.leftChild，那么我们将调用

FIND ( R.leftChild.leftChild, x, R.leftChild.middle );
FIND ( R.leftChild.rightChild, R.leftChild.middle + 1, , R.leftChild.last );

但是，第二个 FIND() 返回 R.leftChild.rightChild.sum 并因此需要恒定的时间，并且问题不会分成两个子问题（严格来说，问题是分开的，尽管一个子问题需要 O(1) 时间解决）。

由于同样的分析适用于 R 的 rightChild，我们得出结论，在 case4 第一次发生后，运行时间 T(h)（h 是树的剩余层）将是

T(h) <= T(h-1) + c (c is a constant)
T(1) = c

产生：

T(h) <= c * h = O(h) = O(log n) (since h is the height of the tree)

因此我们结束证明。

资源

于 2019-01-11T15:41:30.007 回答