我这里有一个算法。
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)”。
你能解释一下原因吗?
最佳答案
堆上的操作需要 O(log(size_of_heap))
。在这种算法的情况下,堆大小为 k
(不包括前几次迭代)。
所以我们得到 O(total_number_of_elements*log(size_of_heap))=O(n*log(k))
。
关于algorithm - 无法定义此算法的运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45417450/