Может быть решена в линейном времени, это было в n ^ 2 раза

Ответ 1

Мое решение, использующее С#, я уверен, что это меньше, чем N ^ 2, но мне нужно посмотреть на него немного дольше. Публикация для критики, пока я это делаю.

public class Employee
{
    public List<Employee> Referred { get; set; }
    public string Name { get; set; }
    public int CountOfRefer { get; set; }
    public bool BeenCounted { get; set; }
    public Employee()
    {
        Referred = new List<Employee>();
    }
}

    public static void main()
    {
        Employee A = new Employee(){ Name="A" };
        Employee B = new Employee(){ Name="B" };
        Employee C = new Employee(){ Name="C" };
        Employee D = new Employee(){ Name="D" };
        Employee E = new Employee(){ Name="E" };
        Employee F = new Employee(){ Name="F" };
        Employee G = new Employee(){ Name="G" };

        A.Referred.Add(B);
        B.Referred.Add(C);
        B.Referred.Add(D);
        D.Referred.Add(E);
        F.Referred.Add(G);
        List<Employee> employees = new List<Employee>()
        {
            A, B, C, D, E, F, G
        };

        foreach (var emp in employees)
        {
            if (!emp.BeenCounted) countRefers(emp);
        }
    }

    private static int countRefers(Employee emp)
    {
        if (!emp.BeenCounted && emp.Referred.Count != 0)
        {
            foreach (var refs in emp.Referred)
            {
                emp.CountOfRefer += countRefers(refs);
            }
        }

        emp.BeenCounted = true;
        emp.CountOfRefer += emp.Referred.Count;
        return emp.CountOfRefer;
    }

В основном при подсчете сотрудника он рекурсирует дерево до тех пор, пока не найдет человека, у которого нет ссылок (что должно быть гарантировано там, так как люди не могут ссылаться друг на друга (думаю, если только 1 человек, игнорируя это случай на данный момент)). Затем, если он должен вычислить кого-либо через рекурсию, он устанавливает флаг, поэтому ему не нужно его снова вычислять.

Ответ 2

Метод графа: сначала постройте ориентированный граф (дерево в этом случае), где каждый node представляет сотрудника и указывает на node сотрудника, который их передал. Это должно принять наихудший случай O (N ^ 2) ((N ^ 2)/2), где N - количество сотрудников. Вы должны, когда вы строите этот график, отслеживать листья этого дерева (сотрудники, которые не ссылались ни на кого), а затем обрезать эти узлы (присваивая ноль их числу рефералов) и добавляя 1 к числу рефералов сотрудников, которые их передали. Затем повторите с новыми листьями, кроме добавления 2 к каждому из их ссылочных узлов количество рефералов. Весь процесс обрезки и подсчета должен также принимать O (N), а в конце все узлы содержат количество рефералов, сделанных каждым сотрудником.

Это предполагает, что на вашем графике нет циклов или странных ситуаций с двумя сотрудниками-сходящимися одинаковыми сотрудниками (т.е. это фактически дерево).

Таким образом, нет, невозможно сделать линейно, если входные данные к проблеме - это двоичные векторы, которые вы описали. Если бы нам дали имена наемных сотрудников с каждым node, тогда возможно было бы O (N).

Ответ 3

Сначала вы можете построить график. Это не должно быть включено в O (n), поскольку ясно, что O (n ^ 2)

Непонятно, если вы оптимизируете дубликаты ссылок (представьте, что все значения равны 1)

На этом этапе вы можете начать с одного node и добавить все упомянутые узлы, например. в битовой маске. Любые значения, которые были добавлены, вам нужно переходить рекурсивно, пока вы не добавите новые узлы.

Количество узлов, которые вы посещаете, равно O (N), так как каждый сотрудник может отсылать одного человека.

Ответ 4

Java Если обман разрешен: enum может представлять граф. Напишите сначала A (B), B (C, D),... и затем измените порядок, чтобы не было прямой ссылки, на которую жалуется компилятор. (Это всегда возможно для нециклических ссылок. Даже проверка времени компиляции против циклических ссылок.)

public class Refers {
    enum RefEnum {
        C(),
        E(),
        G(),
        D(E),
        F(G),
        B(C, D),
        A(B);

        //private final RefEnum[] refs;
        public final int refCount;

        private RefEnum(final RefEnum... refs) {
            //this.refs = refs;
            int n = 0;
            for (RefEnum ref : refs) {
                 n += 1 + ref.refCount;
            }
            refCount = n;
        }
    }

    public static void main(String[] args) {
        for (RefEnum ref : RefEnum.values()) {
            System.out.printf("%s has %d refers%n",
                    ref.toString(), ref.refCount);
        }
    }
}

Однако алгоритм остается O (N²).

Ответ 5

Это дерево (точнее лес). Прочитайте ребра в O (n) времени. Построить дерево в O (n.log(n)). Учитывая node, посещают и подсчитывают потомки в O (n).

Ответ 6

Вы можете сохранить список смежности для всех сотрудников (пространство N). Затем для каждого сотрудника поддерживайте структуру данных, подобную сумме, для всех упомянутых сотрудников. Затем, чтобы подсчитать ссылки для Employee A, вы можете запустить DFS (Depth First Search), начиная с A, который является алгоритмом линейного времени.

Java-код здесь -

http://yogeshsp.blogspot.com/2013/04/graph-api.html

http://yogeshsp.blogspot.com/2013/05/depth-first-search-dfs-graph-processing.html