c# - 这个方法的大 O 表示法是什么？

Question

我在我们的代码库中遇到过这个方法，想知道 Big O 是什么。该方法采用平面列表并创建一棵树，同时分配父项和子项值。

private void AddChildren(Group group, IEnumerable<Group> groups)
{
    foreach (var g in groups)
    {
        if (g.ParentId == group.Id)
        {
            g.Parent = group;
            group.Children.Add(g);
            AddChildren(g, groups);
        }
    }
}

除了确定直接的 n^2(或更糟)方法之外，我已经有一段时间没有完成 Big O 了，但我的看法是这样的:

• 我们正在迭代列表中的每个节点，给我们 n
• 我们正在使用条件来处理被迭代的项目的子集。这里可以有多个匹配项，不知道如何表达那个数字，或者它如何修改对 AddChildren 的递归调用
• 我们有一些简单的作业，我不知道是否需要 +1 修饰符
• 我们正在递归，但不是针对封闭迭代中的每个项目

只是把一些东西扔出去，这样我就可以看看我是否在球场上:

n + (x * n)

其中 x 是 if 循环中的匹配项数。

任何关于这实际上是什么的想法都会很棒，谢谢。

Answer 1

请注意递归函数在每个父子关系中只调用一次。在一个有n个节点的树结构中，有n - 1个这样的关系，所以调用AddChildren() n 次(包括初次通话)。在每次调用中，由于迭代，方法本身执行的工作(不包括递归调用)是 O(n)。因此，总共 O(n^2)。

您可以将复杂度提高到 O(n)，方法是首先将所有组放入 HashMap 中，然后遍历列表一次，查找 HashMap 中的每个父节点。