有序数组和无序数组去重时间复杂度

有序数组查找是O(logn),但是去重的话需要先查找删除位再把删除位后的数据前移，这一步复杂度是O(n)，因此有序数组去重的总复杂度是O(n)

无序数组去重，以C++的duplicate函数为例，先对无序数组排序，时间复杂度是O(nlogn)，然后有序数组去重，则总复杂度是O(nlogn)

摘自https://www.cnblogs.com/dancesir/p/7505730.html，为distinct和group by去重的比较

distinct需要将col列中的全部内容都存储在一个内存中，可以理解为一个hash结构，key为col的值，最后计算hash结构中有多少个key即可得到结果。时间复杂度为O(1)

很明显，需要将所有不同的值都存起来。内存消耗可能较大。

而group by的方式是先将col排序。而数据库中的group一般使用sort的方法，即数据库会先对col进行排序。而排序的基本理论是，时间复杂为nlogn，空间为1.，然后只要单纯的计数就可以了。优点是空间复杂度小，缺点是要进行一次排序，执行时间会较长。

两中方法各有优劣，在使用的时候，我们需要根据实际情况进行取舍。

具体情况可参考如下法则

两个极端：

1.数据列的所有数据都一样，即去重计数的结果为1时，用distinct最佳

2.如果数据列唯一，没有相同数值，用group 最好

使用distinct会将所有的数据都shuffle到一个reducer里面，group by会分组，将数据分布到多台机器上执行。

    最后，对于Hive来说，含有distinct的HQL语句，如果遇到瓶颈，想要调优，第一时间都是想到用group by来替换distinct来实现对数据的去重。