arrays - 排序算法与简单迭代

Question

我刚刚开始学习算法和排序，所以请多多包涵...

假设我有一个包含 50000 个整数的数组。我需要选择其中最小的 30000 个。
我想到了两种方法:
1. 我遍历整个数组并找到每个最小的整数
2.我先对整个数组进行排序，然后简单的选择前30000个。

谁能告诉我有什么区别，哪种方法会更快，为什么？如果阵列更小或更大怎么办？答案会改变吗？

Answer 1

选项 1 听起来像是天真的解决方案。这将涉及遍历数组以找到最小的项目 30000 次。每次它找到最小的，大概它会将该项目交换到数组的开头或结尾。简单来说，这是 O(n^2) 的复杂度。

实际涉及的操作数会少于n^2，因为n每次都在减少。因此，您将有大约 50000 + 49999 + 49998 + ... + 20001，这相当于超过 10 亿(10 亿)次迭代。

选项 2 将采用快速排序或类似算法，通常是 O(n.logn)。

这里很难提供实际数字，因为一些高效的排序算法可能有 O(n^2) 的最坏情况。但是，假设您使用了一个性能良好的保证 O(n.logn)。这将达到 50000 * 15.61，即大约 78 万。

很明显，在这种情况下，选项 2 胜出。

What if the array was smaller or bigger? Would the answer change?

除非阵列变得非常小，否则答案仍然是选项 2。阵列越大，选项 2 就越有利。这就是时间复杂度的本质。 O(n^2) 比 O(n.logn) 增长得更快。

一个更好的问题是“如果我想要更少的最小值怎么办，什么时候选项 1 变得更可取？”。尽管由于众多因素(例如选项 1 与选项 2 中的“一次操作”是什么，以及内存访问模式等其他问题等)，答案稍微复杂一些，但您可以得到简单的答案直接来自时间复杂度。当要选择的最小值的数量低于 n.logn 时，选项 1 将变得更可取。对于包含 50000 个元素的数组，这意味着如果您想选择 15 个或更少的最小元素，则选项 1 胜出。

现在，考虑选项 3，将数组转换为最小堆。构建一个堆是 O(n)，从中删除一个项目是 O(logn)。您将要删除 30000 个项目。所以你有 build 成本加上拆除成本:50000 + 30000 * 15.6 = 大约 520,000。这忽略了每次删除元素时 n 都会变小的事实。它仍然是 O(n.logn)，与选项 2 一样，但它可能更快:您不必费心对不关心的元素进行排序，从而节省了时间。

我应该指出，在所有三种情况下，结果都是按排序顺序排列的最小的 30000 个值。可能还有其他解决方案可以不按特定顺序为您提供这些值。