我为一些二叉树的问题集写了一些代码......代码如下，它一直沿着树向左走，回答是，在回答右边，如果到达一个，则返回外部节点。
用java写的，
public static int price(BinaryTree<Integer> t, boolean[] p) {
Position<Integer> root = t.root(); //1
while (t.isInternal(root)) { //2
int element = root.element(); // 3
if (!p[element]) { //4
root = t.getRight(root);//5
}
if (p[element]) { //6
root = t.getLeft(root); //7
}
}
int price = root.element(); //8
return price; //9
}
在计算 Big O 时，我认为最好在上面的注释中对代码步骤进行编号……我按照这里的示例进行操作
Big O, how do you calculate/approximate it?
所以上面的 1-9 应该等同于这样的东西，其中
C 是常量，??? 是我的循环(其中 N 是给定数据结构的输入数量)C + ??? + C + ??? + C + ??? + C + C + C我的
while 循环是我认为 C*N 或 (O(N)) 而不是现在的 C*N)，我的两个 if 语句应该是(对于索引的时间复杂度 O(1)...和空间复杂度的 O(N)，我现在将坚持时间复杂度)所以现在我应该有(删除
C 元素，因为它们是常量，并不重要)C*N + C + C 时间复杂度和
C*N + C*N + C*N 空间复杂度意思是我有
C*N 或 O (N) 用于时间复杂度和空间复杂度O(3N) 可视为 O(N) ...所以我的问题是，我是否正确地做到了这一点，如果没有，我哪里出错了？
谢谢
编辑:
如果答案为真(是)，则树向左移动，如果给出否，则向左移动。对于树中的 m 个内部节点，内部节点编号为 0 到 m-1。因此，如果在根处给出 no，内部节点 0，因此向右移动，则该内部节点可能是节点 3，因此 boolean 答案在 p[3] 而不是 p[1]，因为 p[1] 是答案对于节点 1，即问题 1。对混淆表示歉意
最佳答案
是和否。
该算法确实是 O(n) ，因为您“触摸”每个元素的次数不会超过恒定次数。
然而，这不是一个严格的界限，或者换句话说 - 它不是 Theta(n) ，而是 Theta(logN) 。 (请记住，大 O 只是一个上限)。
这是因为树是平衡的，您的算法基本上是获取从根到树中某个叶子的路径。请注意，一旦您“选择”向左/向右走，您就永远不会回去。所以基本上你在每个高度“触摸”一个节点的次数是恒定的，使你的算法 O(h) - 其中 h 是树的高度。
由于树是平衡的， h < C * log(n) ，对于一些常量 C - 这使得算法 Theta(logN)