如果是10万个找出10个,那么插入数据库,select就可以搞定(但是面试官不是考你数据库的)。
如果是10亿个找出10000个,就不那么简单了。
先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆中的10000个数就是所需的最大的10000个。
1.拿10000个数建立一个堆heap(顶部放置最小的数,所以是最小堆)
2.取第100001个元素来和堆顶比较,如果小于忽略 如果大于替换,然后调整堆。
3.依次遍历
4.建堆时间复杂度是O(mlogm),算法的时间复杂度为O(nmlogm)(n为10亿,m为10000)
https://blog.csdn.net/zyq522376829/article/details/47686867
https://blog.csdn.net/sky_100/article/details/77675792
O(1):代表CPU处理(循环的)次数随着n的增大,却不发生变化,依然是一次。
i = 0;
O(N):代表CPU处理次数随着n的增大,而线性 y=n 增大。
for(i = 0; i < n; i++)
O(log(N)):CPU处理次数随着n的增大,按照 y=log(N) 增大。
for (int i = 0; i < mid; i++) {
mid = n / 2;
n = mid;
}
O(log(N))的典型场景是二分搜索,每二分一次,需要处理的数据就只剩一半。
所以,每处理过一次,需要处理的数据减半,就是O(log(N))的时间复杂度了。
按这个理解log(N)就是2的对数的意思。log(100) = 10, log(9) = 3
https://zhuanlan.zhihu.com/p/575977815