Что такое обозначение Big O этого метода? - PullRequest
Новая
       2

Что такое обозначение Big O этого метода?

3 голосов
/ 16 июня 2011

Я наткнулся на этот метод в нашей базе кода и удивляюсь, что такое 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);
        }
    }
}

Прошло много времени с тех пор, как я выполнил Big O вне определения прямой n ^ 2 (илихуже), но мой взгляд на это выглядит следующим образом:

  • Мы перебираем каждый узел в списке, давая нам n
  • Мы используем условное выражение для обработки подмножестваэлементы повторяются.Здесь может быть несколько совпадений, и я не знаю, как выразить это число или как он изменяет рекурсивный вызов AddChildren
  • У нас есть несколько простых назначений, и я не знаю, гарантирует ли это +1модификатор
  • Мы повторяем, но это не для каждого элемента в включающей итерации

Просто подбрасываем что-то там, чтобы я мог видеть, был ли я на стадионе:

n + (x * n)

где x - количество совпадений в цикле if.

Любые мысли о том, что это на самом деле было бы замечательно, спасибо.

Ответы [ 2 ]

5 голосов
/ 16 июня 2011

Обратите внимание, что рекурсивная функция вызывается только один раз для родительско-дочерних отношений.В древовидной структуре с n узлами существует n - 1 таких отношений, поэтому AddChildren() вызывается n раз (включая начальный вызов).В каждом вызове работа, выполняемая самим методом (исключая рекурсивный вызов), составляет O (n) из-за итерации.Следовательно, O (n ^ 2) в общей сложности.

Вы можете улучшить сложность до O (n) , поместив сначала все группы в хэш-карту и пройдя поперечислите один раз, просматривая каждый родительский узел в хэш-карте.

1 голос
/ 16 июня 2011

Уже много обсуждается порядок выполнения вашего кода, поэтому я не буду это комментировать. Ответ 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);
    }
}
...