スワッピングの複雑さC＃のディクショナリタイプの引数

Question

私はを持っていますが、Aのオブジェクトは一意であり、オブジェクトはBではありません。

Bのオブジェクトでデータをグループ化するとします。

など。

Dictionary<A,B> input = GenerateInput(); 
List<IGrouping<B,A>> output = input 
           .GroupBy(pair => pair.Value, pair => pair.Key) 
           .ToList(); 

1. アプローチの複雑さとは何ですか？ O（n）？複雑さ= GroupBy操作の複雑さ - 私は値を見つけませんでした。私に教えて、記事へのリンクを提供してください。
2. このスワッピングをより効率的に/エレガントに行う方法はありますか？

PS。変数inputとoutputの型を明示的に書いて、私はoutputがDictioany<,>である必要はないことを示しています。 AまでBまで行くにはコンテナが必要です。

Answer 1

アプローチの複雑さは？

正しく、O（n）です。 GroupByはハッシュコードを使用して値をグループ化します。 Bが良好なハッシング関数を有すると仮定すると、グループのテーブルを構築することは、各グループを「成長させる」償却コストを含むO（n）のコストを償却する。

このスワッピングをより効率的に/エレガントに行う方法はありますか？

O（n）は効率的です。リストの代わりに、グループから辞書を構築することができます。

IDictionary<B,List<A>> output = input 
    .GroupBy(pair => pair.Value) 
    .ToDictionary(g => g.Key, g => g.Select(p.Key).ToList());