这种方法的大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).

您可以先将所有组放在一个hashmap中,然后遍历列表一次,在hashmap中查找每个父节点,从而提高O(n)的复杂性.