二进制搜索树中Java方法的算法开销

Question

我们有Java方法rangeQuery_count(BSTNode,int,int)。给定BST的根（keys int）和区间[a，b]，该方法返回属于该区间的BST的键数

static int rangeQuery_count(BSTNode v, int a, int b) { //a<=b
   if(v==null) return 0;
   if(v.key < a) return rangeQuery_count(v.right, a, b);
   else if(v.key > b) return rangeQuery_count(v.left, a, b);
   else return 1 + rangeQuery_count(v.right, a, b) + rangeQuery_count(v.left, a, b);
}

我必须根据BST的节点数n来确定算法成本的渐近估计。我刚刚开始研究这些主题，我想了解如何计算程序的成本

Answer 1

首先要认识到的是，成本取决于输入参数的特定值，例如，在您的情况下，它取决于搜索树中有多少节点落在间隔内。这里通常的简化假设是计算最坏的情况。在这种情况下，树中的所有节点都位于间隔内。在这种情况下，只要v不为null，您将始终使用else的final子句，您将访问树的每个节点一次，如果树中有n个节点，那么成本将随着n大致呈线性增加