无法定义此算法的运行时间
我在这里有一个算法。无法定义此算法的运行时间
Click here to check algorithm image
它做什么，它遍历数组，发现3个最大数值，并返回它们的总和。 例如，一个数组[1,2,3,4,5]将返回12（3 + 4 + 5 = 12）。
图像中的算法说它是O（nlogk）。但那是我无法理解的。
追随中是我讲第一个for循环的图像透视：
堆的方法 “插入（）” 和 “deleteMin（）”，它们都需要O（LOGN）。因此，在第一个for循环中，它通过添加它们的运行时间（它简单地为O（logn））来生成O（2 * logn）。由于循环的第一个for循环遍历数组中的所有元素，所以第一个for循环的总运行时间为O（nlogn）。
以下是我对第二个观点while循环的图像：
从前面的for循环中，我们如果水平尺寸（）>ķ删除了一些极小值。所以堆中的值的数目是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）
所以我们有O（nlogn）从第一个for循环，并且O（k logn）从第二while循环。显然O（nlogn）大于O（k logn），因为k是某个常数。因此，该算法最后以O（nlogn）结尾。
但答案表示它是“O（nlogk）”而不是“O（nlogn）”。
你能解释一下原因吗？
您对insert（）和deletemin（）运行时的假设是O（log n）是不正确的。 O（log n）中的'n'表示堆中的no.of元素。在这种情况下，它是K.
因此，用于第一环路 - 你有O（2 *的logK）为每一个元件和总将具有为O（n 的logK）和第二环 - O（ķ的logK） 一起的总的复杂性可以是定义为O（n * logk）
对堆的操作需要O(log(size_of_heap))。在这种算法中，堆大小为k（不包括前几次迭代）。我们得到O(total_number_of_elements*log(size_of_heap))=O(n*log(k))。