1

メソッドは次のとおりです。

List<Book> books = new List<Book>();

public List<Book> Shoot()
{
   foreach(var b in books)
   {
       bool find = true;
       foreach(var otherb in books)
       {
           if(otherb != b && otherb.Author == b.Author)
           {
               find = false;
           }
       }

       if(find)
       {
           yield return b;
       } 
   }
}

通常、時間の複雑さは O(books.Count^2) ですが、外側のループに if(find) ステートメントがあり、ループ時間が変わる可能性があります。

だから私の質問は：

  1. この方法の時間計算量はどれくらいですか?
  2. どのように計算しましたか？

あなたの答えをオンラインで待っています。

前もって感謝します。

4

2 に答える 2

3

外側のループ (n) で各本を調べ、内側のループ (n 回) で各外側の本を調べるので、時間の複雑さは O(n^2) になります。

yield リターンはアルゴリズムの複雑さを変更しません。反復子パターンを作成しますが、呼び出し関数からリスト全体をトラバースすると、アルゴのすべての反復を実行します。

C#で使用されるyieldキーワードは何ですか?

アルゴリズムを最適化するには、言及したように、コレクションに対して 2 つのパスを実行できます。最初のパスでは、著者ごとの本の数をハッシュ テーブルに格納し、2 番目のパスでは、著者が複数の本を持っているかどうかを確認します。ハッシュ テーブル (ルックアップに一定の時間がかかると仮定) を取得し、そうであれば本を生成します。

public List<Book> Shoot()
{
    var authors = new Dictionary<string, int>();
    foreach(var b in books) 
    {
        if(authors.ContainsKey(b.Author))
            authors[b.Author] ++;
        else
            authors.Add(b.Author, 1);
    }

    foreach(var b in books) 
    {
        if(authors[b.Author] == 1)
            yield return b;
    }
}

このようにして、O(n) の線形時間複雑度が得られます。この場合、O(n) 余分なスペースが必要になることに注意してください。

于 2012-06-29T00:26:43.853 に答える
1

収量あたりの最悪の場合のパフォーマンスは ですO(n * n)。あなたの最良のケースはO(n)です。著者がランダムにソートされ、固定部分が 1 冊の本のみを執筆すると仮定すると、収量間の平均的なケースは、外側のループの反復にO(n)到達する確率が増加するにつれて指数関数的に減少するためです。(標準の等比級数引数をここに挿入します。)mm

一般に (常にではありませんが!)、人々は平均的なケースに最も関心があります。

ちなみに、この問題を処理する標準的な方法は、すべての著者と彼らが書いた本の数を含む辞書を事前に作成することです。それには時間がかかりますO(n)。その後のyieldは、そのディクショナリのキーを検索して、エントリが1つだけの次のディクショナリを探します。その後の収量の平均時間はO(1)、最悪の場合O(n)は になり、すべての収量にわたる償却平均時間 (一定の割合で 1 冊の本だけを書いたと仮定) は、O(1)収量ごとになります。O(n)利回りごとの現在の実装とは対照的です。

于 2012-06-29T00:38:15.067 に答える