关于树的最近公共祖先算法的时间复杂度分析咨询

先贴出你面试中编写的代码：

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_paths) == 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)

接下来逐个解答你的疑问：

1. 大O表示法中的输入规模n指代什么？ #

你认为n是树的深度，这个其实要看上下文，但在大多数树相关的算法复杂度分析中，n通常指代树的总节点数。当然如果特别约定的话，也会用d表示深度、b表示分支因子，但默认情况下，我们说O(n)指的是复杂度和节点总数线性相关。

如果用深度d来描述，复杂度会和分支因子b挂钩（比如O(b^d)），但用节点总数n的话更直观，因为不管树的形状如何，n直接代表了需要处理的元素总量。

2. find_two_paths采用DFS搜索，是否具有指数时间复杂度？ #

其实不会是指数时间复杂度，这里你可能混淆了递归的复杂度和DFS遍历树的复杂度。

你的find_two_paths是典型的DFS遍历，每个节点只会被访问一次，一旦找到两个目标节点就会提前返回。最坏情况下（比如两个目标节点在树的最底层），我们需要遍历所有节点，此时时间复杂度是O(n)（n为总节点数）。

如果用分支因子b和深度d来表示，树的总节点数大约是b^{d（当树是完全k叉树时），所以O(b}d)其实等价于O(n)，因为n≈b^{d。只有当你把d作为核心输入规模且b固定时，才会写成O(b}d)，但这不属于我们通常说的“指数时间”（指数时间指复杂度是输入规模的指数，比如输入是d，复杂度是2^d），而分析树算法时，输入规模默认是节点数n，所以O(n)才是更准确的表述。

3. get_closest_ancestor的时间复杂度为O(n)，是否因远小于find_two_paths的复杂度可被忽略？ #

首先纠正一下，get_closest_ancestor的时间复杂度不是O(n)，而是O(d)，其中d是树的深度（因为两个路径的长度最多等于树的深度，循环只会遍历到两个路径中较短的那个的长度）。

而find_two_paths的时间复杂度是O(n)，在大多数场景下，d远小于n（比如平衡二叉树中d=logn，和n差距极大），所以get_closest_ancestor的时间复杂度确实可以被忽略，整体算法的时间复杂度由find_two_paths主导，也就是O(n)。

内容的提问来源于stack exchange，提问作者Greg Peckory