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 ループから「ブレーク」を削除すると、時間の複雑さは 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)は列挙子を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) になると思います。

編集: O(n)で動作するListコンストラクターが目的を破っていることについてのMagnusからの良いコメント...

どうですか：

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

letnは長さです_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 を計算するには、2 つの簡単なルールがあります。

  1. f(x) が複数の項の合計である場合、最大の成長率を持つ項が保持され、その他はすべて省略されます。

  2. f(x) が複数の因数の積である場合、定数 (x に依存しない積の項) は省略されます。

休憩なしの必要なステップ数:

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