给定一棵树。如何在不使用大小为 n*n 的二维矩阵的情况下找到树中每对节点之间的距离。我知道 O(n^2) 复杂度的解决方案。
最佳答案
正如我在评论中已经提到的，假设树中每对顶点 (v1,v2,distance) 的输出应该是 v1,v2 - 请注意，有这样的顶点的 n*(n-1) 对。由于 n*(n-1) 在 O(n^2) 中 - 它是输出的大小，因此 它不能做得比 O(n^2) 更好，因此就大 O 表示法而言，您的算法是最佳的。
给定一棵树。如何在不使用大小为 n*n 的二维矩阵的情况下找到树中每对节点之间的距离。我知道 O(n^2) 复杂度的解决方案。
最佳答案
正如我在评论中已经提到的，假设树中每对顶点 (v1,v2,distance) 的输出应该是 v1,v2 - 请注意，有这样的顶点的 n*(n-1) 对。由于 n*(n-1) 在 O(n^2) 中 - 它是输出的大小，因此 它不能做得比 O(n^2) 更好，因此就大 O 表示法而言，您的算法是最佳的。