这个算法为什么具有O(n^2)的时间复杂度？

Question

假设v是树T的一个节点，则节点v的深度可以定义如下：

• 如果节点v是根节点，则v的深度为1。
• 否则，节点v的深度为其父节点深度加1。

基于上述定义，下面的递归算法depth通过在v的父节点上递归调用自身，并将返回值加1，计算了树T中节点v的深度。

算法depth(T, y)：

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

一棵树T的高度等于其所有叶子节点中深度最大的节点的深度。虽然这个定义是正确的，但它并不会导致一个效率高的算法。事实上，如果我们将上述查找深度的算法应用于树T中的每个节点，我们将得到一个O(n²)时间复杂度的算法来计算T的高度。

按照上述语句，为什么时间复杂度是O(n²)？如果我们对每个叶子节点都尝试运行此算法，则需要O(n)的时间，找到最大值也需要O(n)的时间。因此总复杂度应该是O(n)+O(n)=O(2n)==O(n)，对吗？

- ashish

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

- user3386109

Answer 2

如果我们在每个外部节点上尝试此算法，则需要O(n)的时间。但是这是不正确的。您将应用该算法n次，其中每次调用需要O(n)的时间，总共需要O(n^2)的时间。当然，这假定没有缓存/记忆化结果（因此我们正在执行大量重复的工作）。如果有缓存/记忆化结果，那么总共确实是O(n)。请注意保留html标签。

- Cihan

---

如果你应用记忆化，那么你必须考虑到不能直接说是O(n)的边的数量。相反，它应该是O(n+E)，因为我们不知道n和E哪一个占主导地位，因为它们都是1次幂。 - Mateen

这是一棵树，因此根据定义它有N-1条边。@Mateen - Cihan

啊！是的！但对于算法的泛化仍然是正确的。 - Mateen

Answer 3

在渐近符号中，n^2 可能意味着对于每个节点，您正在访问最多 n 或 n-1 个变量数的节点。 让我们考虑一下这个问题：

当您为节点1调用递归函数时，它会立即返回，但是当您为节点5调用它时，需要重新计算从节点1到该节点的所有节点的深度，这意味着您访问了所有其他节点，因为您没有使用记忆化。因此，对于每个节点，您都要访问[1到n-1]个节点。

- Mateen