4

我为一些二叉树的问题集编写了一些代码......代码如下所示，它一直沿着树向下移动，答案是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，您如何计算/近似它？

所以上面的 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。因此，如果在根、内部节点 0 处给出否，因此向右移动，则该内部节点可能是节点 3，因此布尔答案在 p[3] 而不是 p[1]，因为 p[1] 是答案对于节点1，即问题1。为混淆道歉

4

1 回答 1

3

是和不是。

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

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

这是因为树是平衡的，并且您的算法基本上是从根到树中的某个叶子的路径。请注意，一旦您“选择”向左/向右走，您就永远不会回头。所以基本上你只在每个高度“触摸”一个节点的次数是恒定的，这就是你的算法O(h)——h树的高度在哪里。

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

于 2013-08-27T06:58:31.000 回答