从代码中理解大O符号的含义

Question

我为一些二叉树问题编写了一些代码... 代码如下，它会继续向左下走以回答是，向右下走以回答否，并在到达外部节点时返回该节点。

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

当计算大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)...

所以我的问题是，我做得对吗？如果不对，哪里出了问题？

谢谢

编辑：

树向左移动是给出真（是）答案，向右移动是给出否定答案。内部节点从0到m-1编号，其中m个内部节点在树中。因此，如果在根节点处给出否定答案，即内部节点0，则会向右移动，这个内部节点可能是节点3，因此布尔答案在p[3]而不是p[1]，因为p[1]是节点1的答案，即问题1的答案。对此造成的混淆表示抱歉。

- Jim

---

answers是什么？这棵树是否平衡？ - amit

@amit是平衡的，答案是布尔值数组中的“p”，抱歉错误。 - Jim

只就我所见，这段与编程有关的内容是正确的。 - Theolodis

Answer 1

是的和不是。

该算法确实是O(n)，因为您最多只能“触摸”每个元素一定次数。

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

这是因为树是平衡的，您的算法基本上正在获取从根到树中某个叶子的路径。请注意，一旦“选择”向左/右走，您就永远不会回头。因此，您只会在每个高度上“触摸”一个节点一定次数，使您的算法成为O(h) - 其中h是树的高度。

由于树是平衡的，h < C * log(n)，其中C是一些常数 - 这使得算法成为Theta(logN)

- amit

---

我认为应该澄清的是，布尔数组p中的yes/no答案直接对应于内部节点0-m-1，其中m个问题被问到并且数组中有m个答案，0是根节点，因此如果人回答问题0（即根节点）是yes或no，他们会向右走，但是这个问题可能是内部节点3，因此提供的答案是p[3]而不是p[1]，如果你能理解的话...我应该进行编辑，现在重新阅读我的帖子，我会添加进去。 - Jim

另外，我能麻烦您编辑一下，说明在非平衡树中会如何改变吗？ - Jim

@Jim，关键是你修改了根节点并跟随它，因此复杂度如所解释的那样为O(h)。如果树不平衡，则h也可能是n，使其成为Theta(n)。 - amit

“finite”这个词正确吗？不应该是类似于“constant”的东西吗？ - Honza Brabec

@amit 哦，我明白了...那非常有见地，我需要用BigO而不是BigTheta来表示它，但非常感谢你，因为我有点困惑。 - Jim