GroupBy操作的渐近复杂性是什么？

Question

我对未编制索引的数据集上的GroupBy操作的渐近复杂度(大O)感兴趣.最着名的算法的复杂性是什么？SQL服务器和LINQ使用的算法的复杂性是什么？

Answer 1

忽略 group by 正在处理的基本 SQL，当呈现给 GROUP BY 操作本身时，复杂性仅为 O(n)，因为数据是按行扫描并在一次传递中聚合的。它线性缩放到 n（数据集的大小）。

当 Group By 添加到复杂查询时，方程会发生变化，O(n) 成为 Group By添加到整个方程的上限；如果内部复杂查询是这样的，即在基本查询的解析中，数据已经排序，则它可能会更少。

Answer 2

关于 Linq，我想您想了解按复杂性划分的 Linq-to-object 组 ( Enumerable.GroupBy)。

用ILSpy检查实现，在我看来它是O(n)。（.Net Framework 4 系列。）

它枚举一次源集合。对于每个元素，它计算其分组键。然后，它检查哈希表中是否已有映射到元素列表的键，如果缺少，则将键添加到哈希表中。然后它将该元素添加到哈希表中相应的条目列表中。

Answer 3

分组可以在已排序的行上一次性完成（n 复杂度）（n log(n) 复杂度），因此分组依据的复杂度为 n log(n)，其中 n 是行数。如果group by语句中使用的每一列都有索引，则不需要排序，复杂度为n。