Какова будет сложность поиска имени в списке знакомых?

Question

Например, у меня есть класс person, у него есть свойства имени и знакомства, name - строка, в то время как знакомства - массив лиц. Я хотел бы написать метод, который получает имя в качестве параметра и находит его в списке знакомых человека и в списке знакомств и так далее, до тех пор, пока знакомство не станет нулевым или имя не будет найдено.

Ниже приведен код. Также может быть круговая петля, как этого избежать. Заранее благодарим за интерес к вопросу.

class P
{
    public string Name;
    public P[] Acquaintances;
    public P(string name, P[] acquaintances)
    {
        if (String.IsNullOrWhiteSpace(name))
        {
            throw new ArgumentException("Name cannot be null or white space.",
             "name");
        }

        this.Name = name;
        this.Acquaintances = acquaintances;
    }
    public bool FindAcquaintance(string name)
    {
        if (String.IsNullOrWhiteSpace(name))
        {
            throw new ArgumentException("Name cannot be null or white space.",
             "name");
        }
        if (Name.Equals(name))
        {
            return true;
        }
        if (Acquaintances == null || Acquaintances.Length == 0)
        {
            return false;
        }
        foreach (P acquaintance in this.Acquaintances)
        {
            if (acquaintance.Name.Equals(name))
            {
                return true;
            }
            if (acquaintance.FindAcquaintance(name))
            {
                return true;
            }
        }
        return false;
    }
}

Использование

P person = new P("Alex", 
            new P[] {
                new P("Bob",   new P[] { new P("James", new P[] { }) }),
                new P("Kavin", new P[] { new P("Brent", null) })
            });


bool found = person.FindAcquaintance("Brent");

Answer 1

Вы можете выполнить такую ​​операцию за линейное (O (n)) время. Для этого вы должны сохранить свой график в виде списка смежностей

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

Вы можете легко найти человека в списке смежности за линейное время (или даже постоянное время O (1), если вы будете использовать hashMap / hashTable / dictionary), а также его связи.

В противном случае вам придется выполнить обход DFS и сохранить список (набор) посещенных узлов, чтобы избежать циклов. В зависимости от того, какую структуру данных вы будете использовать для посещенного списка, вы можете иметь различные сложности - от O (n) до O (n ^ 2). Но во всех случаях вам потребуется 2n памяти В КАЖДОМ ПУТЕШЕСТВИИ (например, если у вас есть несколько поисков, которые будут выполняться параллельно).