8

以下是我找到第一个共同祖先的算法。但是我不知道如何计算它的时间复杂度，有人可以帮忙吗？

public Tree commonAncestor(Tree root, Tree p, Tree q) {
    if (covers(root.left, p) && covers(root.left, q))
        return commonAncestor(root.left, p, q);
    if (covers(root.right, p) && covers(root.right, q))
        return commonAncestor(root.right, p, q);
    return root;
}
private boolean covers(Tree root, Tree p) { /* is p a child of root? */
    if (root == null) return false;
    if (root == p) return true;
    return covers(root.left, p) || covers(root.right, p);
}
4

2 回答 2

10

好的，让我们从确定该算法的最坏情况开始。covers从左到右搜索树，因此如果您正在搜索的节点是最右边的叶子，或者它根本不在子树中，那么您会得到最坏的情况。此时您将访问子树中的所有节点，O(n)covers也是如此，其中n是树中的节点数。

类似地，当 和 的第一个共同祖先在树的右侧深处时，表现commonAncestor出最坏情况的行为。在这种情况下，它将首先调用两次，在这两种情况下都获得最差的时间行为。然后它将在右子树上再次调用自己，在平衡树的情况下，它的大小为。pqcoversn/2

假设树是平衡的，我们可以通过递归关系来描述运行时间T(n) = T(n/2) + O(n)。使用主定理，我们得到T(n) = O(n)平衡树的答案。

现在，如果树不平衡，在最坏的情况下，我们可能只会为每个递归调用将子树的大小减少 1，从而产生递归T(n) = T(n-1) + O(n)。这种重复的解决方案是T(n) = O(n^2)。

不过，你可以做得比这更好。

例如，我们不是简单地确定哪个子树包含por q，而是确定到andcover的整个路径。这就像，我们只是保留更多信息。现在，平行地穿过这些路径并在它们分歧的地方停下来。这总是。pqO(n)coverO(n)

如果您有从每个节点指向其父节点的指针，您甚至可以通过生成“自下而上”的路径来改进这一点，从而为您O(log n)提供平衡树。

请注意，这是一种时空折衷，因为当您的代码占用O(1)空间时，该算法会O(log n)占用平衡树的O(n)空间，以及一般的空间。

于 2011-05-11T12:20:32.100 回答
0

正如hammar 的回答所表明的那样，您的算法效率很低，因为重复了许多操作。

我会采取不同的方法：如果两个给定节点不在同一个子树中（因此使其成为第一个共同祖先），我将确定从根到两个给定节点的路径，而不是测试每个潜在的根节点节点并比较节点。从根向下的路径上的最后一个公共节点也是第一个公共祖先。

这是Java中的（未经测试的）实现：

private List<Tree> pathToNode(Tree root, Tree node) {
    List<Tree> path = new LinkedList<Tree>(), tmp;

    // root is wanted node
    if (root == node) return path;

    // check if left child of root is wanted node
    if (root.left == node) {
        path.add(node);
        path.add(root.left);
        return path;
    }
    // check if right child of root is wanted node
    if (root.right == node) {
        path.add(node);
        path.add(root.right);
        return path;
    }

    // find path to node in left sub-tree
    tmp = pathToNode(root.left, node);
    if (tmp != null && tmp.size() > 1) {
        // path to node found; add result of recursion to current path
        path = tmp;
        path.add(0, node);
        return path;
    }
    // find path to node in right sub-tree
    tmp = pathToNode(root.right, node);
    if (tmp != null && tmp.size() > 1) {
        // path to node found; add result of recursion to current path
        path = tmp;
        path.add(0, node);
        return path;
    }
    return null;
}

public Tree commonAncestor(Tree root, Tree p, Tree q) {
    List<Tree> pathToP = pathToNode(root, p),
               pathToQ = pathToNode(root, q);
    // check whether both paths exist
    if (pathToP == null || pathToQ == null) return null;
    // walk both paths in parallel until the nodes differ
    while (iterP.hasNext() && iterQ.hasNext() && iterP.next() == iterQ.next());
    // return the previous matching node
    return iterP.previous();
}

两者pathToNode都commonAncestor在 O(n) 中。

于 2011-05-11T13:39:23.880 回答