这个方法的大O表示法是什么

本文关键字：表示 是什么 方法 | 更新日期: 2023-09-27 17:59:23

我在代码库中遇到过这个方法，想知道Big O是什么。该方法采用平面列表并创建一个树，在执行过程中分配Parent和Children值。

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（或更糟）方法之外的大O了，但我对它的看法是这样的：

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

只是扔了一些东西，这样我就可以看看我是否在球场上：

n+（x*n）

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

任何关于这到底是什么的想法都会很棒，谢谢。

这个方法的大O表示法是什么

注意到递归函数在每个父子关系中只调用一次。在具有n节点的树结构中，存在n-1这样的关系，因此AddChildren()被称为n次（包括初始调用）。在每次调用中，由于迭代，方法本身执行的工作（不包括递归调用）为O（n）。因此，总共O（n^2）。

您可以将复杂性提高到O（n），方法是首先将所有组放在哈希图中，遍历列表一次，查找哈希图中的每个父节点。

关于代码的运行时顺序已经有很多讨论了，所以我不会对此发表评论。Aasmund Eldhuset的答案在我看来是正确的。

也许你想要这样的东西，那就是O(n):

void AssignChildrenAndParent(IEnumerable<Group> groups)
{
    var groupById=new Dictionary<GroupId,Group>();
    foreach(Group group in groups)
    {
      groupById.Add(group.Id,group);
    }
    foreach(Group group in groups)
    {
       Group parent=groupsById(group.ParentId);
       group.Parent=parent;
       parent.Children.Add(group);
    }
}

这与原始代码的行为有点不同，因为它修复了所有父子关系，而不仅仅是根以下的关系。

或者，如果你真的想要行为与你的原始代码完全相同的代码（再次O（n），如果哈希操作良好）：

private void AddChildren(Group group, IEnumerable<Group> groups)
{
  var children=groups.ToLookup(group=>group.ParentId);
  AddChildren(group, groups, lookup); 
}
private void AddChildren(Group group, IEnumerable<Group> groups,Lookup<GroupId,Group> lookup)
{
    foreach (var g in lookup[group.Id])
    {
       g.Parent = group;
       group.Children.Add(g);
       AddChildren(g, groups,lookup);
    }
}
相关文章：