| 查看: 566 | 回复: 2 | |||
[交流]
分享一个有意思的算法题，对复杂度分析感兴趣的可以看一下 已有1人参与
|
|
Give an efficient algorithm to find the log n smallest elements in an n by n array of integers if it is known that the columns are in increasing order and the rows are in increasing order. 算法很简单，关键是找到复杂度最小的算法， (越小的复杂度，分析起来越困难） 注意是前log n小的elements，不是第logn小的数。对于后者，典型的面试题，不知道讨论多少次了。 PS: 难道没有人对复杂度分析感兴趣吗？给个算法简单，关键是如何作出分析，得到更好的复杂度。 先抛砖引玉一个：只需要在左上角的logn*logn矩阵中搜索。建一个大小是logn的堆，深度为loglogn,每个元素代表某列的最小值。之后弹出堆顶元素，用堆顶代表行的下一个元素替换，并维护堆。复杂度logn*loglogn。因为只利用了列有序，肯定存在更好的算法。（其实这个问题是个牛人转的，据说存在很tricky的分析方法） [ Last edited by dameng on 2013-11-7 at 16:33 ] |
回复此楼» 猜你喜欢
考研调剂
已经有4人回复
-
281求调剂
已经有4人回复
-
0805 316求调剂
已经有6人回复
-
085601求调剂总分293英一数二
已经有3人回复
-
08工学调剂
已经有17人回复
-
340求调剂
已经有4人回复
-
311求调剂
已经有3人回复
-
食品专硕 一志愿双一流 328
已经有4人回复
-
材料调剂
已经有6人回复
-
300分，材料，求调剂，英一数二
已经有5人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 把发表的综述类论文中的一个方面，再详细综述一下发表出去，算是一稿多投或抄袭吗？
已经有21人回复
- 很有意思的问题：vasp里LSDA+U时候LMAXMIX参数设置问题
已经有10人回复
- 问个热传导问题的计算
已经有15人回复
- 一本很有意思的科普书籍——《你不可不知的50个数学知识》（长见识）【转载】
已经有1126人回复
- 电信的硕士如何科研
已经有11人回复
- 有意思的一个小问题
已经有3人回复
- Abinit计算声子问题
已经有10人回复
- 【讨论】高德纳（高祖）的《具体数学》
已经有5人回复
- 【求助】急求一个关于求和的算法
已经有3人回复
- 【原创】一个简单的kNN分类算法 (k-Nearest Neighbor algorithm) 的C++实现（附源码）
已经有9人回复
- 【重点讨论】Castep中的Empty Band的用处和设置？（参与讨论就有机会赢取大礼包！）
已经有54人回复
- 【在线答疑】UCSF DOCK分子对接和虚拟筛选
已经有42人回复
2楼2013-11-06 23:55:38
3楼2013-11-07 11:46:25
20