伪代码的摊销时间复杂度分析

Question

伪代码：

for level_t in BFS_tree:
    for node1 in level_{t}:
        for node2 in level_{t-1}:
            Do operation

我应该计算这段代码的顺序。这是我目前的想法。
外层循环是线性顺序（在 |G| 上）循环。中间循环是 n^2 阶循环。同样是最内层的循环。
现在我不能继续将这一切相乘，因为中间循环不是所有级别的 n^2。因此，让 Ai 表示每个级别，Bi 表示中间循环的级别中的节点数，Ci 表示最内层循环的每个级别中的节点数。

Ai 上的求和是n。 Bi 上的求和是 n^2。 Ci 的总和是 n^2。我需要 AiBiCi.

的求和

我应该如何继续执行此操作？我考虑过使用 AM/GM 不等式，但求和不会拆分为乘积。

如果您需要更多信息，请告诉我。提前致谢。

Answer 1

我认为分析此代码最有帮助的方法不是计算循环并将它们相乘，而是查看代码的作用并使用它来计算运行时。

前两个循环统称为“遍历树中的每个节点”，对于每个节点，内循环表示“遍历节点的 children”。这意味着我们

访问每个节点，并且
在那个节点做与其度数成比例的工作（children 的数量）。

总的来说，这意味着完成的总工作量受限于树中所有节点的度数之和。计算结果为 O(n)，其中 n 是树中的节点数，与树的形状无关。几种查看方式：

有向图中所有节点的度之和等于图中的边数，n个节点的树恰好有n-1条边。
假设我们在给定节点上执行 k 个工作单元。这意味着该节点有 k children。将一个工作单元推送给每个 children。由于每个节点只有一个 parent 节点，每个节点（根节点除外）在我们完成后都有一个工作单元，因此完成的总工作量为 O(n)。
您上面给出的伪代码等同于运行树上 BFS 的伪代码。运行 BFS 在树上花费时间 O(n)。

伪代码的摊销时间复杂度分析

Amortized Time Complexity Analysis of the pseudocode

algorithm

big-o