在二叉搜索树中递归toString()方法.这个时间复杂度是多少？

Question

我是Java的初学者,正在寻求帮助.

所以我用Java制作了这个二叉树,我应该实现一个方法,按顺序对所有元素进行排序并将它们转换为字符串.它应该看起来像前."[1,2,3,4]".我使用StringBuilder来做到这一点.

我的方法代码看起来像这样:

/**
 * Converts all nodes in current tree to a string. The string consists of
 * all elements, in order.
 * Complexity: ?
 * 
 * @return string
 */
public String toString() {
    StringBuilder string = new StringBuilder("[");
    helpToString(root, string);
    string.append("]");
    return string.toString();
}

/**
 * Recursive help method for toString. 
 * 
 * @param node
 * @param string
 */
private void helpToString(Node<T> node, StringBuilder string) {
    if (node == null)
        return; // Tree is empty, so leave.

    if (node.left != null) {
        helpToString(node.left, string);
        string.append(", ");
    }

    string.append(node.data);

    if (node.right != null) {
        string.append(", ");
        helpToString(node.right, string);
    }
}

所以我的问题是,我如何计算时间复杂度呢？此外,如果有任何关于如何使这种方法更好的建议,我很乐意欣赏它.

Answer 1

最简单的答案是:O(n).您每次访问每个节点并执行一(1)项工作.计算结果如下

O(a*n)

因为我们忽略了常数因素,所以简单的答案就是

O(n)

但是.人们也可以争辩说,你做的只是多一点:null每次你去一个没有叶子的地方你都会回来.这又是一(b)项工作量.

让我们暂时把那些看不见的叶子称为.遵循这个想法,树中的每个值都是一个有一个或两个不可见叶子的节点.

所以现在,我们要做以下事情(对于每个节点):

a       | if a node has two child nodes
a + b   | if a node has one child node
a + 2b  | if a node has no child node.

对于最坏情况的二叉树(完全不平衡),我们有(n-1)个节点有一个子节点,一个节点没有子节点:

  "1"
    \
    "2"
      \
      "3"
        \
        "4"

所以,计算是

     (n-1)*(a+b) + b
 <=> an + bn - a - b + b
 <=> n(a+b) + b

  => O(an + bn)  // we ignore `+ b` because we always look at really big n's

幸运的是,即使在最糟糕的情况下,复杂性仍然是线性的.只有常数高于简单答案.在大多数情况下 - 通常在需要Big-O来比较算法时 - 我们甚至忽略了这个因素,我们很高兴地说,算法时间复杂度是线性的(O(n)).