GroupBy运算的渐近复杂性是什么? [英] What's the asymptotic complexity of GroupBy operation?

问题描述

我对未索引数据集上的GroupBy操作的渐近复杂度(大O)感兴趣.最知名的算法的复杂性是什么，SQL Server和LINQ使用的算法的复杂性是什么?

I am interested in the asymptotic complexity (big O) of the GroupBy operation on unindexed datasets. What's the complexity of the best known algorithm and what's the complexity for algorithms that SQL servers and LINQ are using?

推荐答案

可以对已排序的行(n log(n)复杂度)进行一次遍历(n复杂度)分组，因此group by的复杂度为n log(n)，其中n是行数.如果group by语句中使用的每一列都有索引，则不需要排序，并且复杂度为n.

Grouping can be done in one pass (n complexity) on sorted rows (nlog(n) complexity) so complexity of group by is nlog(n) where n is number of rows. If there are indices for each column used in group by statement, the sorting is not necessary and the complexity is n.

这篇关于GroupBy运算的渐近复杂性是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！