algorithm - 无法定义此算法的运行时间

Question

我这里有一个算法。

Click here to check algorithm image

它的作用是遍历一个数组并找到 3 个最大值并返回它们的和。例如，数组 [1,2,3,4,5] 将返回 12 (3+4+5=12)。

图像中的算法说它是 O(nlogk)。但这是我无法理解的。

以下是我对图中第一个for循环的看法:

Heap 的方法“insert()”和“deleteMin()”，它们都需要 O(logn)。所以在第一个 for 循环中，它通过添加它们的运行时间来使 O(2*logn)，这就是 O(logn)。由于第一个 for 循环遍历数组中的所有元素，因此第一个 for 循环的总运行时间为 O(nlogn)。

以下是我对图中第二个 while 循环的看法:

从前面的 for 循环中，如果 h.size() > k，我们删除了一些最小值。所以堆中值的数量当前是k。 “sum=sum+h.min()”需要 O(logn)，因为如果我知道的话，在堆中搜索最小值需要 O(logn)，而“h.deleteMin()”也需要 O(logn)，因为它必须再次搜索并删除。通过添加它们的运行时间，O(2*logn) 也是如此，这就是 O(logn)。因为我们只迭代这个 while 循环 k 次，因为有 k 个元素，所以第二个 while 循环导致 O(k*logn)

所以我们从第一个 for 循环得到 O(nlogn)，从第二个 while 循环得到 O(klogn)。很明显，O(nlogn) 大于 O(klogn)，因为 k 是某个常数。因此，该算法最终以 O(nlogn) 结束。

但答案是“O(nlogk)”而不是“O(nlogn)”。

你能解释一下原因吗？

Answer 1

堆上的操作需要 O(log(size_of_heap))。在这种算法的情况下，堆大小为 k(不包括前几次迭代)。

所以我们得到 O(total_number_of_elements*log(size_of_heap))=O(n*log(k))。