如何找到这两个函数的运行时间呢？

Question

我熟悉大 O 表示法和运行时间，大多数时候我可以识别算法的运行时间，但我不确定这个算法。我在这里处理一棵树。

第一种方法：

static boolean containsData(TreeNode treeRoot, String data) {
    if(treeRoot == null)
        return false;
    if(data.equals(treeRoot.data))
        return (true);
    else if((data.compareTo(treeRoot.data))<0)
        return(containsData(treeRoot.left, data));
    else
        return(containsData(treeRoot.right, data));
}

第二种方法：

static boolean containsData2(TreeNode treeRoot,String data){
    if (treeRoot != null) {
        if (treeRoot.data.contains(data)) {
            return true;
        } else {
            return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data); 
        }
    }
    return false;   
}

我会说这两种方法都是 O(n) 我看不出其中一种方法是 O(log(n)).

Answer 1

你的第一个方法是 O(n) 如果底层树 不平衡 并且这种情况会发生在 所有数据按升序或降序插入.

它将是O(logn)，如果底层树像红黑树、AVL树一样平衡而不管数据及其插入顺序。

你的第二种方法对于不平衡树是 O(n) ，对于平衡树它是 O(n) 只有当该树不包含给定的数据，导致您的第二种方法在这种情况下最终遍历整个树。如果它确实包含，那么时间总是 O(logn)

Answer 2

如果树有 n 个单元格，那么你将继续 O(n)（所有单元格，一次），这是正确答案。不要混淆树的Height，如果树是平衡的，那可以是O(log n)。

Answer 3

这两种方法本质上做的是同一件事，就是遍历树寻找某个项目。这两种方法都向左或向右搜索项目，并一直这样做直到到达树的末端。正如@Sumeet 已经提到的，我们不能真正给你一个确切的 Big-O 运行时间，因为我们不知道树是否平衡。在平衡二叉树的情况下，both方法的搜索时间应该是O(lgn)。但是，在最大不平衡树的情况下，元素的高度 和元素数量 都将是 n，因此搜索时间将是 O(n)。如果您能弄清楚树木的类型，我们或许可以缩小确切的运行时间范围。

Answer 4

如果树不平衡，这两种方法都有最坏的情况运行宁时间 O(n)。

如果树是平衡的，第一个将在 O(log n) 中运行。

即使对于平衡树，第二种方法仍然需要 O(n)，因为如果在右半部分找到记录，它会遍历两个子树。它实际上按排序顺序对所有记录进行全面扫描，直到找到记录。实际运行时间取决于记录的大小。小记录会更快找到，大记录将需要 O(n)。平均值是 O(n).

如何找到这两个函数的运行时间呢？

How to find the running time of these two functions?

java

algorithm

binary-tree