2

有没有最便宜的方法可以将 ICollection 与自身进行比较。

这是我的代码：

        public IEnumerable<Pet> speciesChecker()
        {
            foreach (Pet pet in _pets)
            {
                bool wantedSpecies = true;
                foreach (Pet pet2 in _pets)
                {
                    if (pet2 != pet && pet.Species == pet2.Species)
                    {
                        wantedSpecies = false;
                        break;
                    }
                }
                if (wantedSpecies) yield return pet;
            }
        }

我的代码的时间复杂度是多少，我所知道的是它小于 O(N^2)，如果我从内部 foreach 循环中删除“break”，时间复杂度将为 O(N^2) . 如果我错了，请纠正我。

4

4 回答 4

2

这是我的看法：

var q = list.GroupBy (l => l.Species)
          .Where (l => l.ElementAtOrDefault(1) == null)
          .Select (l => l.Key)

GroupBy将在内部使用 HashSet，因此 O(N)
ElementAtOrDefault(1)只需将枚举数移动一步，因此不会是 O(n)

于 2012-01-17T00:28:33.497 回答
1

我认为这段代码做同样的事情。在这种情况下，这是一个 O(N) 算法。诀窍是将宠物存储在按物种索引的字典中。

    public IEnumerable<Pet> speciesChecker()
    {
        var species = new Dictionary<Species, List<Pet>>();
        foreach (Pet pet in _pets)
        {
            // create the list if it doesn't exist
            if (!species.ContainsKey(pet.Species))
                species[pet.Species] = new List<Pet>();
            species[pet.Species].Add(pet);
        }

        // foreach species, if there is only one pet of that species, then return it
        foreach (var speciesPets in species.Values)
        {
            if (speciesPets.Count() == 1)
                yield return speciesPets.First();
        }

        yield break;
    }
于 2012-01-16T23:53:46.097 回答
1

你也可以使用类似下面的东西，它也应该是 O(N)：

public IEnumerable<Pet> speciesChecker ()
{
    _pets.GroupBy (p => p.Species)
         .Select (g => new List<Pet> (g))
         .Where (l => l.Count == 1)
         .SelectMany (l => l);
}

额外的Select (g => new List<Pet> (g)) 可能是多余的，但我相信这将有助于避免第二次迭代整个分组逻辑，我相信这会导致 O(N^2) 。

编辑： Magnus 对在 O(n) 中运行的 List 构造函数违背了目的的良好评论......

怎么样：

public IEnumerable<Pet> speciesChecker ()
{
    var groups = _pets.GroupBy (p => p.Species);

    foreach (var grp in _pets.GroupBy (p => p.Species))
    using (var e = grp.GetEnumerator ()) {
        if (!e.MoveNext ())
            continue;

        var first = e.Current;

        if (e.MoveNext ())
            continue;

        yield return first;
    }
}

我认为这是尽可能优化的，并且可以在 O(n) 中工作。我们也避免使用IEnumerable<T>.Any ()orIEnumerable<T>.Count ()扩展方法。

想法？

于 2012-01-17T00:01:57.430 回答
0

让n是长度_pets collection

带中断所需的步骤数：

1+2+3+...+n = n*(n+1)/2 =n^2/2 + n/2 = O(n^2) (for each pet in _pets);

从 wiki 计算 O 有两个简单的规则：

  1. 如果 f(x) 是多项之和，则保留增长率最大的一项，而忽略其他所有项。

  2. 如果 f(x) 是多个因子的乘积，则省略任何常数（乘积中不依赖于 x 的项）。

不间断的所需步骤数：

n+n+n+...+n = n^2 = O(n^2)
于 2012-01-17T00:04:48.473 回答