algorithm - 该算法的复杂度如何为 O(n^2)？

Question

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

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

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

算法depth(T, y):

• 第一步:如果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个，以此类推。所以访问的 parent (P)总数为1+2+3+...+(n/2).

使用 formula for the sum of natural numbers我们有 P = (n/2)(n/2 + 1)/2 = (n^2 + 2n)/8。忽略常数因子 (8) 和次要项 (2n)，我们看到 P 为 O(n^2)。