我是 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);
}
}
所以我的问题是,如何计算时间复杂度?另外,如果有任何关于如何改进此方法的建议,我将非常感激。
最佳答案
最简单的答案是:O(n)
。您访问每个节点一次并执行一 (a) 量的工作。计算结果如下
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))。
关于java - 二叉搜索树中的递归 toString() 方法。这个的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5037885/