GroupBy操作的渐进复杂度是什么？

Question

我对GroupBy操作在未索引数据集上的渐近复杂度（大O）感兴趣。目前已知最优算法的复杂度是多少？SQL服务器和LINQ使用的算法复杂度又是多少？

- Jakub Šturc

---

请注意，SQL和LINQ中的GroupBy是两个非常不同的操作。 - Gert Arnold

Answer 1

关于Linq，我想你想了解的是Linq-to-object中关于复杂度的分组（Enumerable.GroupBy）。

通过使用ILSpy检查实现，我发现它是O(n)的。（.Net Framework 4系列。）

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

- Frédéric

---

+1，但值得注意的是哈希表操作只有预期平摊O(1)；最坏情况是O(n)，这使得GroupBy的最坏情况为O(n^2)，但在实践中不太可能发生。另外值得注意的是，一些哈希表实现可以平均访问多个元素，同时仍然是O(1)，因为平均访问的元素数量不随n增长，尽管我认为.NET使用了负载因子1，所以实际上只有平均1个元素。 - Kevin

Answer 2

忽略Group By操作所使用的基础SQL，当呈现给Group By操作本身时，复杂度只是O(n)，因为数据是按行扫描并在一次聚合中聚合。它与数据集大小n成线性比例。

当Group By添加到复杂查询中时，方程式会改变，O(n)成为Group By对整个方程式所增加的上限；如果内部复杂查询的解析已经排序，则可能会更少。

- RichardTheKiwi

---

由于没有索引，当数据排序时，您已经花费了O(N log N)的时间进行排序。(吹毛求疵：它与n成线性比例关系，即与数据集的大小成比例，而不是与n的大小成比例) - R. Martinho Fernandes

O(n)并不是常数时间，它是线性时间。O(1)是常数时间。 - user7116

@sixlettervariables：我知道。要执行GroupBy，您必须遍历所有项（这是O（n）），并针对每个项决定它属于哪个组（这不是O（1））。 - Jakub Šturc

@Legatou: 我同意...我应该说比较的复杂度是 O(k) 和 O(1)。 - user7116

@Squirrelsama 当k是常数时（例如，它实际上是O(15)，这是你的字段长度），O(k)可以在与行数n有关的上下文中化简为O(1)。 - NetMage

Answer 3

在已排序的行(nlog(n) 复杂度下), 可以一次性完成分组(n复杂度), 因此group by的复杂度为 nlog(n), 其中n为行数。如果在group by语句中使用了每列的索引，则不需要进行排序，复杂度为n。

- JosefN