了解从代码

Question

衍生出来的大O符号我为一些二叉树问题编写了一些代码...代码如下，它继续沿着左边的树回答yes，右边的答案no并返回外部节点，如果它到达一个。

用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 
} 

在计算大OI认为最好号码在评论中码以上步骤...我也跟着从这里

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) .. 。

所以我的问题是，我是否正确地做了这件事，如果不是我哪里出错了？

谢谢

编辑：

树向左移动提供一个真正的（是）回答或右侧给出一个否定的。内部节点编号从0到m-1，用于树中m个内部节点。因此，如果在根，内部节点0处给出no，并且因此向右移动，则该内部节点可能是节点3，因此布尔答案在p [3]而不是p [1]，因为p [1]是答案对于节点1，即问题1.道歉混淆

Answer 1

是和否。

该算法确实是O(n)，因为您“触摸”每个元素的次数不会超过常数。

但是，这不是一个严格的限制，换句话说 - 它不是Theta(n)，它是Theta(logN)。 （请记住，大O只是一个上限）。

这是因为树是平衡的，并且您的算法基本上从树中的根到树叶中获取路径。请注意，一旦你“选择”去左/右，你永远不会回去。所以基本上你只需在每个高度上“触摸”一个节点的次数是固定的，这就使得你的算法O(h)-其中h是树的高度。

因为树是平衡的，h < C * log(n)，对于某一常数C - 这使得算法Theta(logN)