java - 理解源自代码的大 O 符号

Question

我为一些二叉树问题集写了一些代码......代码如下它一直沿着树向下移动，左边的答案是"is"，右边的答案是“否”，如果到达一个，则返回外部节点.

用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 or O(N) 时间复杂度和空间复杂度

O(3N) 可以认为是O(N)...

所以我的问题是，我这样做是否正确，如果没有，我哪里出错了？

谢谢

编辑:

如果答案为真(是)，树会向左移动；如果答案为否，树会向右移动。对于树中的 m 个内部节点，内部节点从 0 到 m-1 编号。因此，如果在根、内部节点 0 处给出 no，并因此向右移动，则该内部节点可能是节点 3，因此 boolean 答案在 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)