该算法如何具有 O(n^2) 的复杂度？

Question

设 v 为树 T 的一个节点。 节点 v 的深度可以定义如下：

• 如果 v 是根，则 v 的深度为 1。
• 否则，v 的深度为 1 加上 v 的父级的深度。

基于上述定义，递归算法深度，如下面的算法所示，通过在 v 的父节点上递归调用自身，并在返回值上加 1 来计算 Tree 的节点 v 的深度。

算法depth(T, y)：

• 第 1 步：如果 T.isRoot(v)，则返回1
• 第 2 步：否则，返回 1 + depth(T, T. parent(v))

树 T 的高度等于 T 的外部节点的最大深度。虽然这个定义是正确的，但它并没有导致一个有效的算法。事实上，如果我们将上述深度寻找算法应用于树 T 中的每个节点，我们将推导出 O(n ² ) 时间算法来计算 T 的高度。

根据上面的说法，它怎么可能是 O(n ² )？如果我们在每个外部节点上尝试这个算法，那么它需要 O(n)，并且找到最大值它需要 O(n)。所以总复杂度应该是 O(n)+O(n) = O(2n)==O(n)，对吧？

Answer 1

该算法的最坏情况是一棵树不平衡。例如，如下图所示的树：

上面的树有 5 个外部节点和 5 个内部节点，所以正好有一半的节点是外部节点。从 A 开始，有一个父节点。从 B 开始，有 2 个，以此类推。所以P访问的父节点 ( )的总数是1+2+3+...+(n/2)。

使用我们有的自然数和的公式P = (n/2)(n/2 + 1)/2 = (n^2 + 2n)/8。忽略常数因子 (8) 和次要项 (2n)，我们看到它P是 O(n^2)。