证明/解释给定算法的时间复杂度为O(h+k)。其中 h 是树的高度,k 是 x 和 y(含)范围内的节点数。
我知道,如果 k=0(范围内没有任何项目),那么算法会简单地遍历树的高度,因此 O(h)。我也知道一个节点是否在它对它的两个 child 而不是其中一个 child 重复出现的范围内。但这似乎有双重效果,所以我对如何证明/解释这一点感到困惑。
INRANGE-TREE-WALK (v, x, y)
if v != NIL
if v.key < x
INRANGE-TREE-WALK(v.right, x, y)
else if v.key 〈= y
print v.key
INRANGE-TREE-WALK (v.left, x, y)
INRANGE-TREE-WALK (v.right, x, y)
else
INRANGE-TREE-WALK(v.left, x, y)
最佳答案
我假设这棵树是一棵二叉搜索树。
您可以查看调用该函数的当前节点的深度,然后注意对于任何给定的深度,访问的深度不会超过一个节点 v v.key < x
.
虽然这可能会在不同的深度发生多次,但声称在树中的相同深度,这种情况永远不会发生超过一次。
暂时假设这个声明是错误的,并且在树中的一个特定深度 d 算法访问两个节点 a 和 b,它发现 a.key < x
和 b.key < x
。我们还选择 a 和 b 使得 a.key <= b.key
,即 a 在 b 的左边。
首先,请注意访问 a 和 b 的唯一方法是首先访问这些节点的共同祖先 p,因为我们有 x <= p.key <= y
。否则没有办法沿着树下的两个不同的 Twig 走。
但由于这是一棵二叉搜索树,p 右子树中的所有节点 v 的值都为 v.key >= P.key
,因此为 v.key >= x
。对于节点 b 也是如此。但这与 b.key < x
的前提相矛盾。
所以,我们有证据表明该函数不会被同一级别的两个节点调用,并且它们都有 v.key < x
。因此,在整个算法的执行过程中,该条件只能找到 h 次。
对于 v.key > y
的情况也可以得出相同的结论。
x <= p.key <= y
有多少次为真?由于该算法永远不会访问同一个节点两次(因为它只访问任何已访问节点的子节点),因此此条件为真的次数等于 k。
保持 v == NIL
的次数。这永远不会超过访问节点数加一。
将所有这些加在一起,我们得到了不超过 2(2h + k)+1 的单个函数调用的数量,并且假设执行一个函数调用 -排除递归调用 -- 是常数,我们得到 O(h+k) 的时间复杂度。
关于algorithm - 证明/说明算法的时间复杂度为O(h+k),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44830632/