algorithm - 该算法的复杂度如何为 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)，对吧？

标签： algorithmdata-structures

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)。