问题是：
给出了n个未分类元素的数组。对于K的每个值，请建议在最坏情况下，计算k最小的算法有效算法值：
a。k = 30
b。k = n/3
c。k = logn
对于每种情况，对算法进行简短描述，并简要分析最坏以及最好的情况复杂性。编辑：只要我们以有效的方式计算k，我们就不必对未排序的数组进行排序。
好，所以我完全不确定这一点，
a）对于k = 30，我建议我们第一次找到最小数字30次，这是第二次，这是n -1，直到n -29。O（n）中的30个最低数字，（对吗？）
b）考虑仅在最坏情况下排序算法（heapsort或mergesort，取决于用户是否会使用额外的空间），然后只计算第一个N/3，因此我可以在O中进行此操作（因此nlogn）步骤。
c）考虑要从这个数组制作最小的堆，因此要堆积它会花费我O（n），之后我需要使用堆的删除（这将使我o（logn）完全logn times op me o（logn）因此，它将是n logn^2，这意味着o（n）（对吗？）
所以您知道，我已经考虑过，仍然不确定我的答案。预先感谢！
我们可以用来计算k最小值的有效算法涉及堆的使用。我们将首先从建造最小堆开始。当我们建造最小堆时，我们将创建一个完整的二进制树。要创建堆，我们将遵循另一种算法。我们首先将元素添加到堆的底部。然后，我们将此元素与其父元素进行比较，如果小于父母，我们可以停止。如果没有，我们会更改元素并重复。构建最小堆树的运行时间为O（n）的最坏情况（可能是O（logn），具体取决于实现的类型）。
完成此操作后，最小元素将位于二进制树的根部，因此我们可以从顶部将其删除。但是，如果我们正在寻找最小的元素，则必须在删除最小元素（k次）后每次"堆"图。当我们堆积时，我们将重新安排当前的树，以便它再次变成堆。一个庞大的操作的运行时间为O（logn），我们正在这样做k次，因此此部分的最糟糕的情况是O（klogn）。
当我们结合两个操作时，我们最终的最坏情况的时间复杂性是o（n klogn）。
对于每种情况，最坏的情况运行时间复杂性将保持不变。
对于任何算法，您需要对第1个30个项目进行排序。您只需要与最大现有数字进行比较的第31项。如果更大，您什么都不做1比较）。如果较小，则必须与30/2（平均）进行比较。然后删除最大的。