算法的时间复杂度分析

Question

在一次采访中，我被要求编写一个函数，给定一棵树和树中的两个节点，将最接近的祖先返回给这两个孩子。你知道吗

这是我的密码：

two_paths = []

def get_closest_ancestor(path1, path2):

    for i in xrange(min(len(path1), len(path2))):
        if path1[i] != path2[i]:
            return path1[i-1]

def find_two_paths(root, a, b, path = []):
    global two_paths

    newpath = path[:]

    newpath.append(root)

    if len(two_nodes) == 2:
        return

    if root == a:
        two_paths.append(newpath)
    if root == b:
        two_paths.append(newpath)

    for child in root.children:
        find_two_paths(child, a, b, newpath)


if __name__ == "__main__":

    find_two_paths(root, a, b)
    print get_closest_ancestor(two_paths)

然后我被要求给出我刚写的算法的大O复杂度。你知道吗

所以我们有2个函数，find_two_paths，和get_closest_ancestor。你知道吗

我的第一个问题是，我们在这里接受什么作为输入。在我们的大O符号中n是什么？你知道吗

我想我们把树的深度看作n

find_two_paths显然执行DFS搜索，所以我认为我们已经有了指数级的时间复杂度。你知道吗

我们能用它是一棵树的事实，说它的复杂性是O(b^n)，其中b是树的分支因子，而n是树的深度吗？你知道吗

我们能说它是O(2^n)吗？你知道吗

我们是否可以忽略get_closest_ancestor函数，因为它是O(n)，并且被find_two_paths严重压倒？你知道吗

Answer 1

这绝对不是O(2^n)。快多了。对于图问题，通常将n定义为树中的节点数。让我们总结一下你的算法的作用：

1. 从根目录中查找a，然后查找b（记住指向它们的路径）
2. 逐项比较这些路径，直到发现不一致为止（并返回最后一个公共节点）

对于步骤1，DFS is ^{}。每个节点访问一次，因此性能与节点数成正比。这里需要注意的一点是，您实际上短路了（尽管是通过使用全局短路），所以您不考虑所有节点。当然，最坏的情况是a和b是我们访问的最后两个节点，因此DFS将是O(n)。你知道吗

对于步骤2，最坏的情况是路径在最后一个节点（a和b是同级节点）之前是相同的。因此，最差的性能将与最长的可能列表的长度成正比。现在，我们可以批判性地思考第1步，并推断出访问每个节点的O（n）总是大于或等于第2步中的最长路径（因此总体上O(n)将占主导地位，这将是O(n)时间），但是让我们彻底讨论一下。如果我们对树有一些保证（比如它是一个平衡的二叉树），我们可以说最长的路径是O(log n)，因此比较这两条路径最坏的情况是O(log n)。但是我们没有这样的保证。我们可以更一般地说，如果我们可以近似地说，图的分支因子（每个节点的子节点的平均数目）是b，那么我们可以近似地说，最长的路径是O(log_b n)。但是对于一般树（最坏的情况是链表），路径的长度是O（n）。因此，步骤2也是最坏情况O（n）。你知道吗

因此，这个O(n)的整体运行时。你知道吗

Answer 2

树度量复杂度通常是节点数。缺乏精确回答的假设，特别是关于树中节点的顺序。一个简单的通用解决方案是构造从node1到根的path1，然后构造从node2到根的path2，同时在每个步骤验证当前节点是否在path1中。当然，如果你的树是有序的，一些优化显然是可能的。你知道吗

假设你的n节点树有确切的度数d，那么构造path1最坏需要log\d（n）步，构造path2最坏也需要log\d（n）步，但是对于它的每一步，你需要搜索到path1，它需要log\d（n）。最后需要对数d（n）^2。你知道吗