linq .whereのBig Oとは何ですか？

Question

私は、リストから項目をフィルタリングする場所についていくつか比較しています。私はそれをO（n）にするか、.Where（）を使って直接行うことは確信しています。単純なデータセットのI made a simple example to test .Where()。 n = 100の項目があり、関数BigO()の行でデバッガを実行すると、100倍になります.Where（）もO（n）です。私が把握できなかったのは、操作中にデータが保存されていた場所で、複雑さが増しているかどうかはわかりませんでした。

何かが見つからない、または.Where（）O（n）ですか？

public class ListerFactory 
{ 

public class Lister 
{ 
    bool includeItem { get; set; } 
} 

List<Lister> someList { get; set; } 

public ListerFactory() 
{ 
    someList = new List<Lister>(); 
    BuildLister(); 
}  

public void BuildLister() 
{ 
    for(int i = 0; i < 100; i++) 
    { 
    var inc = new Lister(); 
    inc.includeItem = i % 2; 
    someList.Add(inc); 
    } 
    BigO(); 
} 

public void BigO() 
{ 
    someList = someList.Where(thisList => thisList.includeItem == true).ToList(); 
} 
} 

Answer 1

Where()はO（1）である。それは実際には何の仕事もしません。

Where()によって返されたコレクションのルーピングはO（n）です。 ..

あなたが見ているO（n）はToList()の結果です。は O（n）です。
O（n ）アルゴリズムにWhere()クエリを渡すと、コールバックはn 回実行されます。 （アルゴリズムがどこにもキャッシュしないと仮定して）

これは遅延実行と呼ばれます。

すべてのLINQプロバイダーではないにしても、これはほとんどの場合に当てはまります。 LINQプロバイダが熱心にすべての呼び出しを実行することは意味がありません。

---

オブジェクトへのLINQの場合、ソースコレクションの列挙子はO（n）であることを前提としています。
O（n）よりも悪い（つまり、MoveNext()がO（1）よりも悪い場合）反復する奇妙なコレクションを使用している場合は、Where()がそれに限定されます。

より正確には、Where()クエリを列挙する時間の複雑さは、元の列挙の時間の複雑さと同じです。

同様に、私はコールバックがO（1）であると仮定しています。
そうでない場合は、コールバックの複雑さに元の列挙の複雑さを掛ける必要があります。

Answer 2

もちろん、収集元によって異なります。

Where()へのクエリで条件に一致する候補が検索されるため、アルゴリズムがO(1)であると@SLaksは同意しません。その意味では、最悪の場合O(n)となり、Where句の前にコレクション全体を生成する作業量はnになります。

しかし、彼はコレクションを生成するアルゴリズムに依存する点を持っています（例えば、リストを作成するビルドがすでにO(n)で、コレクション内の項目数がnの場合）。照合があるかどうかは、必ずしもO(1)ではありません。イールドアルゴリズムがO(n)であり、一致アルゴリズムO(m)がO(n*m)である場合は、

例えば整数の集合ください：あなたはWhere()句でこれを行うことができ、少なくとも2回発生するすべての整数を返すようにしたい場合は

int[] test = new int[] {1,2,3,4,5,6,7,8,9,10,7,5,0,1,5,6}; 

を：

test.Where(x => test.Count(y => x == y) >= 2); 

アルゴリズムはO(n^2)

です。第2に、レイジー設定でコレクションを構築することもできます。

public IEnumerable<int> GenerateCollection() { 
    //some very complex calculation, here replaced by a simple for loop 
    for(int i = 0; i < 150; i++) { 
     yield return i; 
    } 
} 

ただし、アルゴリズムは最初にリストを生成します。時間の複雑さはO(n)です。あなたは後にコレクション全体を反復処理する場合

お知らせしかしtimecomplexityはまだO(n*m)とないO(n*n*m)です。それは、一度候補がマッチしたら、それは再考されないからです。