在一次面试中很偶然的遇到了一次竞技编程的问题。
很遗憾我两个问题都没有遇到过,然后也没能给出一个正确的“最优解”。
毕竟承认咱们确实还玩的不算好,大学时也没能小组出线。
不过面试官似乎并不像gxxgle一样比较注重思考的过程,而是比较想看到是不是能迅速的给出最优解。

0.问题:大数据中求最大的前100项

假设有足够大的一列数值数据中,如何迅速的找出排名前100的最大的数值。

1.我的解法:

时间复杂度:O(n)
最糟糕的时间复杂度:O(n^2)
空间复杂度:O(n)

这个是我面试时候几分钟之内考虑出来的。
类似于quick sort,不过只继续求最大的一个分组。那么理想最佳的情况下,每次都有一半的比某一个中点数值大的数值被排到大的一个分组。到达最后的分组的大小是100的时候,就可以中止。属于剪掉枝条的一种优化。
那么他的计算复杂度显然就是(n + n/2 + n/4 + … + n(1/2)^(n-8) + 1),最后的1是较大数组的个数是100-200区间的时候,最后一步的计算的计算复杂度。可以粗略的用等比数组的和的形式来表现。
在这里,最后1次计算时的分组数据个数200要比2^7=128要大,所以需要计算的次数是(logn) - 7,
根据等比数组计算公式,[1]

不过这里是a = n, r = 1/2, k = {1, n-8}

当n足够大的时候,计算复杂度是O(2n) = O(n)
我的天,所以这个算法也是一个O(n)的算法= =||||
面试的时候应该吹一波的,不过这个算法不具有实用性罢了。
(因为O(n)的memory size实在是太大了,实际操作需要通过DB操作进行优化)

注解:
(1)不能用merge sort这个安定sort的原因是,这个不能在分组大小是100的时候,2个分组能保证一定是前一个的每一个数值都比后一个分组的要大。
(2)这个最糟的情况和quick sort一样,每次的分组的数据个数都是1,n-1,这样的时间复杂度一定是O(n^2)
(3)还有一种很糟的情况,就是大的一组的个数少于100。这就需要别的优化了。比如再在小的一组进行计算or etc..

2.网络流传的最优解法[2]

时间复杂度:O(kn)
空间复杂度:O(k)

网络流传的这个其实很好理解。就是拿来一个按大小排好的min-heap。然后挨个过滤一遍,前100个就挨个放进去,每个数字插入的时间是O(k)。(k=100)。那么之后每次只需要比较数字的最小的那个数字就可以了。然后只要比最小的数字小,就可以放进去。那么事实上每次操作只需要查看数字的O(1)和把它放到heap里面的插入时间O(k)就可以。
真的太简单了= =||

3.后记

(不过面试的时候我忘记了等比数组的和公式,所以只好说是我的解法的时间复杂度O((nlogn)/2) = =|||)
估计面试官在想,这么简单的题都做不出来…..

[1]wikipedia 等比数列
[2]stackoverflow Retrieving the top 100 numbers from one hundred million of numbers
[3]Math Expression by Powered by MathJax


Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)