我刚开始学习算法和排序,所以请容忍我。。。
假设我有一个50000个整数的数组。
我需要选出最小的30000个。
我想到了两种方法:
一我遍历整个数组并找到每个最小的整数
2.我首先对整个数组进行排序,然后简单地选择前30000个。
有谁能告诉我有什么区别,哪种方法更快,为什么?
如果阵列更小或更大呢?答案会改变吗?

最佳答案

选项1听起来像是天真的解决方案。它需要通过数组查找最小的项30000次。每次它找到最小的一个时,可能会将该项交换到数组的开头或结尾。基本上,这是O(n ^ 2)复杂度。
实际涉及的操作数将小于n^2,因为n每次都会减少。所以你大概有50000+49999+49998+…+20001,相当于超过10亿(10亿)次迭代。
选项2将采用类似quicksort或类似的算法,通常是o(n.logn)。
在这里,很难提供实际的数据,因为一些有效的排序算法的最坏情况是o(n^2)。但是假设你使用了一个行为良好的,保证是o(n.logn)。这将达到50000*15.61,约为78万。
很明显,在这个案例中,选项2获胜。
如果阵列更小或更大呢?答案会改变吗?
除非数组变得非常小,否则答案仍然是选项2。数组越大,选项2就越有利。这就是时间复杂性的本质。o(n^2)比o(n.logn)增长快得多。
一个更好的问题是“如果我想要更少的最小值,什么时候选项1变得更好?”尽管答案有点复杂,因为有很多因素(例如,在选项1和选项2中,构成“一个操作”的选项,加上内存访问模式等其他问题),您可以直接从时间复杂度中得到简单的答案。当要选择的最小值的数目降到n.logn以下时,选项1将变得更可取。在50000个元素数组的情况下,这意味着如果要选择15个或更少的最小元素,那么选项1将获胜。
现在,考虑一个选项3,将数组转换为最小堆。构建堆是O(n),从堆中移除一个项是O(logn)你要移除30000件物品。所以你有建筑成本加上移除成本:50000 + 30000×15.6=大约52万。这忽略了这样一个事实:每次删除元素时,n变小它仍然是o(n.logn),类似于选项2,但可能更快:您不必费心对不关心的元素进行排序,从而节省了时间。
我应该提到,在这三种情况下,结果将是按排序顺序排列的最小30000个值。可能还有其他的解决方案可以不按特定顺序给出这些值。

09-26 03:52
查看更多