我对未索引数据集上的GroupBy操作的渐近复杂度(大O)感兴趣。最著名的算法的复杂性是什么,SQL Server和LINQ使用的算法的复杂性是什么?
可以对已排序的行(n log(n)复杂度) 进行一次遍历(n复杂度)分组,因此分组的 复杂度为n log(n),其中n是行数。如果group by语句中使用的每个列都有索引,则不需要排序,并且复杂度为n。