无法定义此算法的运行时间
Can't define runtime of this algorithm
我这里有一种算法。
Click here to check algorithm image
它的作用是遍历一个数组并找到 3 个最大值和 return 它们的总和。
例如，数组 [1,2,3,4,5] 将 return 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)).
您关于 insert() 和 deletemin() 运行时间花费 O(log n) 的假设是不正确的。 O(log n) 中的 'n' 表示堆中的 no.of 个元素。在这种情况下它是 k。
因此，对于第一个循环 - 每个元素都有 O(2*logk)，总和将有 O(nlogk) 和第二个循环 - O(k logk)
总复杂度可以一起定义为 O(n*logk)
我这里有一种算法。
Click here to check algorithm image
它的作用是遍历一个数组并找到 3 个最大值和 return 它们的总和。 例如，数组 [1,2,3,4,5] 将 return 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)).
您关于 insert() 和 deletemin() 运行时间花费 O(log n) 的假设是不正确的。 O(log n) 中的 'n' 表示堆中的 no.of 个元素。在这种情况下它是 k。
因此，对于第一个循环 - 每个元素都有 O(2*logk)，总和将有 O(nlogk) 和第二个循环 - O(k logk) 总复杂度可以一起定义为 O(n*logk)