Geek asks and answers

What is the Big O designation of this method?

I came across this method in our code base and wonder what Big O is. The method takes a flat list and creates a tree, assigning the values ​​"Parent and Child" when it goes.

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);
        }
    }
}

It has been some time since I did Big O outside the definition of direct methods n ^ 2 (or worse), but my approach to this is as follows:

  • We repeat each node in the list, giving us n
  • We use a conditional expression to handle a subset of repeating elements. There may be several matches, and they don’t know how to express this number, or how it modifies the AddChildren recursive call
  • We have a few simple assignments, and I don’t know if the +1 modifier guarantees this.
  • We recurs, but this is not for every element in the attached iteration

- , , :

n + (x * n)

x - if.

, , , .

+3
2

, . n n - 1 , AddChildren() n ( ). , ( ), O (n) - . , O (n ^ 2) .

O (n), - , node hashmap.

+5

, . 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);
    }
}
+1

More articles:


All Articles