GroupBy操作の漸近的な複雑さは何ですか？

インデックスされていないデータセットのGroupBy操作の漸近的複雑さ（big O）に興味があります。最もよく知られているアルゴリズムの複雑さと、SQLサーバーとLINQが使用しているアルゴリズムの複雑さは何ですか？GroupBy操作の漸近的な複雑さは何ですか？

SQLとLINQのGroupByは、非常に異なる2つの操作です。 –

GROUP BY操作自体に表示されるときに、グループが作業している基本SQLを無視すると、データは1行でスキャンされ、1回の集計で集計されるため、複雑さはO（n）にすぎません。それは線形にn（データセットのサイズ）に比例します。

複雑なクエリにGroup Byを追加すると、O（n）はグループBy が全体の式にを追加する上限になります。内部の複雑なクエリがベースクエリの解決でデータが既にソートされているようなものであれば、それは少なくなる可能性があります。

2011-02-03 18:16:20 RichardTheKiwi

インデックスがないため、データがソートされると、すでにO（N log N）をソートしています。（ニックピック：それはnに線形にn、すなわちnのサイズではなく、データセットのサイズにスケールする） –

@Martinho - 私は英語構文エラーを修正した。 – RichardTheKiwi

残念だがこれは間違っている。データセットを反復処理するときは、与えられた行/オブジェクトに入れたいグループを決めなければなりません。私は一定の時間内にどのようにグループ選択を行うことができるのか分かりません。 –

Linqについては、Linqからオブジェクトへのグループについて複雑さ（Enumerable.GroupBy）を知りたいと思います。

ILSpyで実装を確認すると、O（n）と表示されます。（.NET Framework 4シリーズ）

ソースコレクションを1回列挙します。各要素に対して、グループ化キーを計算します。次に、キーがすでに要素リストにマップされているハッシュテーブルにあるかどうかを確認し、ハッシュテーブルにキーがない場合は追加します。次に、要素をハッシュテーブル内の対応するエントリリストに追加します。

2017-04-08 21:26:48

答えて