algorithm - 这种找到 N 个数中最大的 K 个的方法的复杂性是什么

Question

在this post on how to find the K largest of N elements第二种方法是:

1. 将前 k 个元素存储在临时数组 temp[0..k-1] 中。
2. 在temp[]中找到最小的元素，让最小的元素为min。
3. 对于arr[k]到arr[n-1]中的每个元素x如果 x 大于最小值，则从 temp[] 中删除最小值并插入 x。
4. 打印 temp[] 的最后 k 个元素

虽然我理解这种方法，但我不理解他们的计算O((n-k)*k) 的时间复杂度。

从我的角度来看，您正在对 n-k 元素进行线性遍历，并对每个元素进行一次比较。然后可能会替换 K 元素的临时数组中的一个元素。

更具体地说，他们计算的*k方面在哪里O((n-k)*k) 的时间复杂度从何而来？为什么他们将 n-k 乘以那个？

Answer 1

让我们考虑在第k次迭代时:

arr[k] > min(temp[0..k-1]

现在您将用 arr[k] 替换 min(temp[0..k-1])。

现在您再次需要计算 temp[0..k-1], 的更新 min，因为那会发生变化。它可以是更新后的 temp[0..k-1]

中的任何数字

所以在最坏的情况下，你每次都更新最小值，因此 O(k)。

因此，时间复杂度 = O((n-k)*k)