java多线程    Java入门    vsftp    ftp    linux配置    centos    FRP教程    HBase    Html5缓存    webp    zabbix    分布式    neo4j图数据库    

十万大小的数据集,从中选择10个最大的元素怎么做

如果是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


This entry was posted in JAVA. Bookmark the permalink.
月小升QQ 2651044202, 技术交流QQ群 178491360
首发地址:月小升博客https://java-er.com/blog/10data-10-find/
无特殊说明,文章均为月小升原创,欢迎转载,转载请注明本文地址,谢谢
您的评论是我写作的动力.

Leave a Reply